Rohan comes to the IET campus for attending the various workshops in Invento 2K16. Workshops are going to conducted in rooms numbered from 1 to n. There are multiple ways to go from room i to room j. These ways are directed in nature, that is these ways are specific from room i to room j, but not from room j to room i.
Travelling through a path consumes 1 unit of energy. Rohan has only K units of energy. During travel, he can use at most K units of energy.
Given number of ways to travel from each room to every other room, you need to find out the ways of travelling from each room to every other room but consuming at most K units of energy.
Output the number of ways modulo 109 + 7
Input Format
First line contains 2 space separated integers, n and K
Next n lines contains n space separated integers each line, in which jth element in ith line denotes the ways from room i to room j
Output Format
Output n lines, in which each line contains n space separated integers such that jth element in ith line denotes the ways from room i to room j
Constraints
- 1 ≤ n ≤ 50
- 1 ≤ K ≤ 109
- 1 ≤ Number of ways ≤ 109
- The directed graph formed may contains self-loops and multiple edges
0-length path from 1 to 1 = 1
1-length path from 1 to 1 = 1, Using self loop on 1
2-length path from 1 to 1 = 2, One path using only self loop on 1 and second using the path 1-2-1
So total resulting path for 1 to 1 = 1 + 1 + 2 = 4
In similar way we can find result for other pairs of rooms too.
