MATPROD2 - Symmetric matrix 2
[Note: Symmetric Matrix is an easier version of this problem; you should try to solve it before this one.]
You are given an N x 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).
Input: 4 5 -4 -3 -4 2 -3 -6 1 -8 -4 1 -10 -6 2 -8 -6 0 Output: 308822466