404772: GYM101628 I In the clouds

Tiago lives in a street with N houses, numbered from 1 to N, in which the first one is his. He decided to get out of Codeforces and visit a friend, but his head is stuck in a problem for several days. Because of that, he is bit distracted and is not paying attention to where he is going.

The walk can be represented by K steps, where if he is in house i in a step, is the probability of him being at house j in the next step. He wants to know what is the expected value of the house where he'll stop, but he is too distracted to solve this problem.

The first line of input consists of two integers N and K (1 ≤ N ≤ 100, 1 ≤ K ≤ 10⁹). The next N lines contain each N integers, where the j-th number in the i-th line is A_ij (0 ≤ A_ij ≤ 10⁶) and the sum in each line is 10⁶.

The answer can be represented as an irreducible fraction . Print the integer P * Q^- 1 modulo 10⁹ + 7 (Q^- 1 is the modular inverse of Q modulo 10⁹ + 7).

2 2
500000 500000
500000 500000

500000005

4 24255
283383 274729 386113 55775
167247 49080 415640 368033
449168 182769 352198 15865
127605 304475 230640 337280

96636490

2 2
0 1000000
1000000 0

1

2 1
0 1000000
1000000 0

2