荷取融合

题目背景

作为一款Rougelike类游戏,TODR具有丰富的装备系统。每一款装备独特的外观和华丽的特效,上百种各有效果的印记,复杂的炼成调和分解融合系统都塑造了这款游戏极高的游戏性。 现在你的装备刷到了满级,需要和其他装备融合来继续成长,当然,你需要让河城荷取将你原装备中的印记抽取出来以便和新装备合成。

题目描述

已知原装备有 $n$ 个印记槽,每个印记槽中有无限多的一种印记,第 $i$ 个印记槽中的这种印记价值为 $a_{i}$。 河城荷取会用机械臂抽取印记槽内的印记,每一次抽取时,机械臂会向下抓取,从正下方的印记槽中抽取出一个印记,之后机械臂会向右移动或停留在原地(如果移动,那么可以移动任意格),开始时机械臂的位置任意,但是任意时刻机械臂都必须在某个印记槽上。 河城荷取会进行 $k$ 次抓取,抓取结束后,你获得的总收益等于抓上来的 $k$ 个印记价值的乘积。 假设河城荷取进行的一切操作都是随机的,那么你能获得的收益的平均值是多少呢? 由于答案可能不是整数,你只需输出答案对 $\text{19260817}$ 取模后的结果。

输入输出格式

输入格式


第一行两个整数 $n,k$ ,表示印记槽的个数和抓取的次数。 第二行 $n$ 个正整数 $a_{i}$ ,表示每个印记槽内印记的价值 。

输出格式


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

输入输出样例

输入样例 #1

3 2
3 1 2

输出样例 #1

16050685

输入样例 #2

6 3
1 1 4 5 1 4

输出样例 #2

16509294

说明

#### 样例 $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$ ![](https://cdn.luogu.com.cn/upload/pic/42182.png)