### 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

## Comments (Search)

lamiomnion Jul 30, 2014 - 9:26:31 am UTC Missing path in explanationAlexon Jul 30, 2014 - 7:44:25 pm UTC Re: Missing path in explanation