T4

给定 $nm$ 个有序（可被分辨，即使值相同也是为两个本质不同的）的数 $a_1,a_2,\cdots,a_{nm}$，将这些数分成若干无序的组使得每组数的个数为 $m$ 的倍数，每个数都在且仅在一个组 $G$ 内。

例如，如果 a 为 1,1,2 , 则 {(第一个)1,2} , {(第二个)1} 与 {(第二个)1,2} , {(第一个)1} 为不同的分组方案，但 {(第一个)1,2} , {(第二个)1} 与 {(第二个)1} , {(第一个)1,2} 为相同的分组方案。

定义一个合法的分组方案 $P$ 的权值为 $\prod\limits_{G \in P}\sum\limits_{x \in G}a_{x}$。

求所有分组方案的权值和对 $10^9+7$ 取模的结果。

输入格式

第一行两个整数 $n,m$。

第二行 $nm$ 个整数依次表示序列 $a_i$。

输出格式

一行一个整数表示所有方案权值的总和。

样例1输入

3 1
3 3 9

样例1输出

222

样例2输入

2 2
10 6 7 5

样例2输出

602

样例3见下发文件

请点击文件下载

ex_d1.in

ex_d1.out

ex_d2.in

ex_d2.out

ex_d3.in

ex_d3.out

数据范围

对于 $10\%$ 的数据，满足 $n,m \le 4$。

对于 $25\%$ 的数据，满足 $n \le 100$。

对于 $40\%$ 的数据，满足 $n \le 500$。

对于另外 $20\%$ 的数据，满足 $m=1$。

对于所有数据满足： $1 \le n \le 1500$，$1 \le m \le 100$，$0 \le a_i < 10^9+7$。