Woburn Team Practice '07

We all know of the centuries-long battle between the monkeys and the cows. In an attempt to defeat the cows once and for all, the monkeys are holding a meeting to discuss battle strategy. The land in which the monkeys live consists of ~N~ ~(3 \le N \le 15)~ towns, numbered from ~0~ to ~N-1~. Some towns are connected by one-way roads. It is known that all the monkeys live in town ~0~ and that the meeting will be held in town ~N-1~.

It is the day of the meeting, and all the monkeys are mingling with each other. To their amazement, they discover that each of the monkeys traveled from town ~0~ to town ~N-1~ along a path that didn't visit any town more than once. They also discover that each monkey traveled a path distinct from all other monkeys. Finally, they come to realize that there could not be any more monkeys at the meeting, otherwise one of the earlier conditions would have been violated. How many monkeys are at the meeting?

Input Specification

The first line of the input file contains a single integer ~T~ ~(1 \le T \le 10)~, indicating the number of test cases to follow.

Each test case begins with a single line containing the integer ~N~. The next ~N~ lines each contain ~N~ space-separated integers, either 0 or 1, giving the one-way connections between towns in the land (0 means no connection exists, 1 means a connection does exist).

Output Specification

A single integer that is the number of monkeys at the meeting. This number should be outputted modulo ~13\,371\,337~.

Sample Input

1
5
0 1 1 0 0
1 0 0 0 1
0 1 0 1 1
1 1 1 0 1
1 0 0 0 0

Sample Output

5

Explanation

There are ~5~ monkeys at the meeting. The paths taken are:
~0 \to 1 \to 4~
~0 \to 2 \to 4~
~0 \to 2 \to 1 \to 4~
~0 \to 2 \to 3 \to 4~
~0 \to 2 \to 3 \to 1 \to 4~
There cannot be any more monkeys at the meeting because the paths they travelled wouldn't be distinct or would visit a town more than once during their trip.