Cho một đồ thị đơn, có hướng \(G\) với \(N\) đỉnh, được đánh số \(1,2,3,4,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), bạn được cho \(1\) số nguyên \(a_{i,j}\) thể hiện sự kết nối có hướng giữa hai đỉnh \(i\) và \(j\). Nếu \(a_{i,j}=1\) thì đỉnh \(i\) được nối với đỉnh \(j\) theo chiều từ \(i\) đến \(j\), nếu \(a_{i,j}=0\) thì không tồn tại kết nối giữa hai đỉnh \(i,j\).

Yêu cầu: Tìm số đường khác nhau có độ dài là \(K\) trong \(G\), biết rằng mỗi con đường này có thể đi qua một cạnh nhiều lần.

Vì đáp số có thể lớn nên cần lấy mod \(10^9+7\) trước khi in ra

Input

• Dòng thứ nhất chứa hai số nguyên \(N,K(1\le N\le 50,1\le K\le 10^{18})\)

• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,n}(1\le i\le N, a_{i,j}\in \left\{0,1\right\})\)

Output

• In ra đáp án sau khi đã lấy mod \(10^9+7\)

Example

3 3
0 1 0
1 0 1
0 0 0

3