MATPROD - Symmetric matrix

[NOTE: A harder version of this problem is Symmetric Matrix 2; you may want to try it once you solve 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 ≤ 5), 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 by 1000000007 (== 109+7).

Example

Input:
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
Date:2014-04-29
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2020-10-19 16:56:31
ez
2015-01-30 03:03:03 Allaoua
Same as above, I compiled and run the code on the given example (and format), and had the same outputs as the example (even on ideone), but it had given WA after 08 runs here (no compile errors or TLE though), is there anything missing in the problem description?

Last edit: 2015-01-30 03:09:01
2014-09-26 05:38:38 S.Y.P.Lai
I need some hint about the reason why my code got WA. I might be misunderstanding the problem. When I try to use the "direct" method to calculate the sum, I got WA instead of TLE. I can get 308822466 using the given example.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.