#659. 荷取融合
荷取融合
题目描述
已知原装备有 个印记槽,每个印记槽中有无限多的一种印记,第 个印记槽中的这种印记价值为 。
河城荷取会用机械臂抽取印记槽内的印记,每一次抽取时,机械臂会向下抓取,从正下方的印记槽中抽取出一个印记,之后机械臂会向右移动或停留在原地(如果移动,那么可以移动任意格),开始时机械臂的位置任意,但是任意时刻机械臂都必须在某个印记槽上。
河城荷取会进行 次抓取,抓取结束后,你获得的总收益等于抓上来的 个印记价值的乘积。
假设河城荷取进行的一切操作都是随机的,那么你能获得的收益的平均值是多少呢?
由于答案可能不是整数,你只需输出答案对 取模后的结果。
输入格式
第一行两个整数 ,表示印记槽的个数和抓取的次数。
第二行 个正整数 ,表示每个印记槽内印记的价值。
输出格式
一个整数,表示 次抓取结束后的收益的平均值。
样例
3 2
3 1 2
16050685
6 3
1 1 4 5 1 4
16509294
题目来源:洛谷 P5131