## MATPROD2 - Symmetric matrix 2

no tags

[Note: Symmetric Matrix is an easier version of this problem; you should try to solve it before this one.]

You are given an N matrix mij such that mij == mji for i, j = 1, ..., N. We would like to compute the value of Note that in the above expression we are going over K indices i1, ..., iK that run over the values 1, ..., N, while summing over the product of all the K*(K-1)/2 possible matrix elements that we can form with these indices.

### Input

The first line of the input contains two integers N and K (2 ≤ N ≤ 100 and 2 ≤ K ≤ 10), representing the number of rows and columns of the matrix mij and the number of sums in the formula above, respectively. The following N lines contain N integers each, being the j-th number in the i-th line the value of mij (-10  ≤ mij ≤ 10 and mij == mji for i, j = 1, ..., N).

### Output

Print a single line with the result of the calculation. Because this number can be very big, output its remainder modulo division by1000000007 (== 109+7).

### Example

```Input:
4 54 5
-4 -3 -4 2
-3 -6 1 -8
-4 1 -10 -6
2 -8 -6 0

Output:
308822466```

 Added by: Fidel Schaposnik Date: 2014-04-29 Time limit: 1s-2s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64