小 P 得到了 $nm$ 本有序的书，第 $i$ 本书有一个权值 $a_i$，下标从 $1$ 开始。

作为一个卷怪，他想把这些数分成若干无序的组以便学习，使得分到每组的书的数量都是 $m$ 的倍数。

小 P 认为一个分组方案的价值为所有组内的书权值和的乘积。

现在小 P 想知道对于所有分组方案，其价值的和是多少。由于这个数太大，所以小 P 只想知道它对 $10^9+7$ 取模的结果。

两个分组方案不同当且仅当存在两本书在一个分组方案中被分进了同一组而另一个分组方案中不在同一组。

输入格式

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

第二行 $nm$ 个整数依次表示每本书的权值 $a_i$。

输出格式

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

样例一

input

3 1
2 3 4

output

85

样例二

input

2 2 
1 3 5 6

output

169

限制与约定

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

• $\text{Subtask 1(10pts): }$ 满足 $n,m \le 4$。
• $\text{Subtask 2(20pts): }$ 满足 $m=1$。
• $\text{Subtask 3(15pts): }$ 满足 $n \le 100$。
• $\text{Subtask 4(15pts): }$ 满足 $n \le 500$。
• $\text{Subtask 5(40pts): }$ 满足 $n \le 1500$。