Woburn Team Practice '07

Strategy Meeting

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 ≤ N ≤ 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 to 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

The first line of the input file contains a single integer T, between 1 and 10, inclusive, indicating the number of testcases to follow.

Each testcase 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

A single integer that is the number of monkeys at the meeting. This number should be outputted modulo 13371337.

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–1–4
0–2–4
0–2–1–4
0–2–3–4
0–2–3–1–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.

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Aug 26, 2010

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3