Description

已知原装备有 $n$ 个印记槽，每个印记槽中有无限多的一种印记，第 $i$ 个印记槽中的这种印记价值为 $a_{i}$。

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

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

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

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

Input Format

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

第二行 $n$ 个正整数 $a_{i}$ ，表示每个印记槽内印记的价值 。

Output Format

一个整数，表示 $k$ 次抓取结束后的收益的平均值。

3 2
3 1 2

16050685

6 3
1 1 4 5 1 4

16509294

Hint

样例 $1$ 解释:

机械臂开始可以停在三个槽上方。

先后抓取的印记槽的位置可以是 $(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)$ 六种,每一种抓取方案的收益分别是 $9,3,6,1,2,4$ ，平均值为 $\frac{25}{6}$，在 $\text{mod 19260817}$ 的意义下等于 $16050685$

数据范围:

$a_{i}<19260817$