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.


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).


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).


4 5
4 5 -4 -3 -4 2 -3 -6 1 -8 -4 1 -10 -6 2 -8 -6 0 Output: 308822466

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