Little P has obtained $nm$ ordered books, where the $i$-th book has a weight $a_i$, with indices starting from $1$.
As a hard-working student, he wants to divide these books into several unordered groups for study, such that the number of books in each group is a multiple of $m$.
Little P defines the value of a grouping scheme as the product of the sums of the weights of the books in each group.
Now, Little P wants to know the sum of the values of all possible grouping schemes. Since this number can be very large, he only wants to know the result modulo $10^9+7$.
Two grouping schemes are considered different if and only if there exist two books that are in the same group in one scheme but not in the other.
Input
The first line contains two integers $n$ and $m$.
The second line contains $nm$ integers, representing the weights $a_i$ of the books in order.
Output
Output a single integer representing the sum of the values of all schemes.
Examples
Input 1
3 1 2 3 4
Output 1
85
Input 2
2 2 1 3 5 6
Output 2
169
Constraints
For all data, $1 \le n \le 1500$, $1 \le m \le 100$, $0 \le a_i < 10^9+7$.
- Subtask 1 (10 pts): $n, m \le 4$.
- Subtask 2 (20 pts): $m = 1$.
- Subtask 3 (15 pts): $n \le 100$.
- Subtask 4 (15 pts): $n \le 500$.
- Subtask 5 (40 pts): $n \le 1500$.