[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 m_ij such that m_ij == m_ji 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 i₁, ..., i_K 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 m_ij 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 m_ij (-10  ≤ m_ij ≤ 10 and m_ij == m_ji 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 (== 10⁹+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