#659. 荷取融合

荷取融合

题目描述

已知原装备有 nn 个印记槽,每个印记槽中有无限多的一种印记,第 ii 个印记槽中的这种印记价值为 aia_{i}。

河城荷取会用机械臂抽取印记槽内的印记,每一次抽取时,机械臂会向下抓取,从正下方的印记槽中抽取出一个印记,之后机械臂会向右移动或停留在原地(如果移动,那么可以移动任意格),开始时机械臂的位置任意,但是任意时刻机械臂都必须在某个印记槽上。

河城荷取会进行 kk 次抓取,抓取结束后,你获得的总收益等于抓上来的 kk 个印记价值的乘积。

假设河城荷取进行的一切操作都是随机的,那么你能获得的收益的平均值是多少呢?

由于答案可能不是整数,你只需输出答案对 19260817\text{19260817} 取模后的结果。

输入格式

第一行两个整数 n,kn,k,表示印记槽的个数和抓取的次数。

第二行 nn 个正整数 aia_{i},表示每个印记槽内印记的价值。

输出格式

一个整数,表示 kk 次抓取结束后的收益的平均值。

样例

3 2
3 1 2
16050685
6 3
1 1 4 5 1 4
16509294

题目来源:洛谷 P5131