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 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?
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
giving the one-way connections between towns in the land (
0 means no
1 means a connection does exist).
A single integer that is the number of monkeys at the meeting. This number should be outputted modulo ~13\,371\,337~.
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
There are ~5~ monkeys at the meeting. The paths taken are:
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.