Holidays P92544

Enric wants to go on holidays. He will first fly to any of n cities. Let’s call c that initial city. He will rent a car in c, spend h days on a roadtrip, and finally fly back home from c. He can visit any city more than once in his route, but he will stay at least one day in each city he visits, everytime he visits it, with one exception: the first day he will not visit c.

Given that he only cares about the order of the visited cities, but not about the number of days spent at every city, in how many ways can Enric plan his holidays? Apart from c, he wants to visit at least another city. Consider that the travel time between cities is negligible.

Input

Input consists of several cases. Every case begins with n and h, followed by n rows, one for every city i, with n numbers r_ij each, with a 1 if there is a direct road from city i to j, and a ‍0 otherwise. Note that roads may be one-way only, that is, the given adjacency matrix can be asymmetric. Assume 2 ≤ n ≤ 30, 1 ≤ h ≤ 10⁹, and r_ii=0.

Output

For every case, print the number of ways to spend h days on holidays, modulo 10⁹ + 123.