NSIT ACM SAARC Prelims

Archit needs to save his girlfriend from the evil vampire. He is in Room 1 and his girlfriend is captured in Room N. He also knows the distance between each room and the girlfriend's room. He has decided only to move in such a way that he gets strictly nearer to his destination (absolute distance). Formally, he moves to a room which is nearer to room N at each step.

There are several tunnels that connect some of the rooms. A tunnel can be used in a bi-directional way.

Help him find out the number of ways by which he could reach the Nth room and save his girlfriend.

If it is impossible for him to save his girlfriend, output "impossible" (without the quotes.)

Input

First line denotes the number of test cases T (<= 50).

Each test case begins with a single integer N (1 < N <= 1000).

Then follows N space separated integers (D[i]) denoting the distance between Room i and Room N. (D[i] <= 10000)

The following N lines contain N space separated integers each.(F[i][j])

The jth column on ith row is 1 if there exists a tunnel between Room i and Room j and 0 otherwise.

Note that F[i][j] = F[j][i] because of bidirectional tunnels.

and D[N] = 0

Output

Output the number of ways for him to reach the Nth Room or "impossible" otherwise.

Since, the results can be very large output the number of ways modulo 124027.

Example

Input:
1
4
9 3 5 0
0 1 1 0
1 0 1 1
1 1 0 0
0 1 0 0

Output:
2