B. Fruit Blast
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Busy Beaver downloaded a new game on his phone and needs your help to play it!

In this game, a level consists of $$$N^2$$$ starting fruits in a line, each of a type numbered $$$1$$$ through $$$N$$$, with $$$N$$$ fruits of each type. A move consists of the following:

  • Choose a subset of $$$N$$$ fruits in the line, not necessarily consecutive, such that the chosen fruit types are $$$k, k+1, \dots, N, 1, \dots, k-1$$$ in order for some $$$1 \le k \le N$$$, and such that the starting fruit type $$$k$$$ is different from that of every previous move.
  • Remove the chosen fruits from the line.
Busy Beaver wins the level if he performs $$$N$$$ moves that remove every fruit from the line. (Formally: a level is winnable if it can be partitioned into $$$N$$$ subsequences, each a distinct cyclic shift of $$$1, 2, \dots, N$$$.)

You are given an array of $$$N^2$$$ integers $$$a_1, \dots, a_{N^2}$$$, each in the range $$$[0, N]$$$. Count the number of ways to replace each $$$0$$$ in the array with an integer in $$$[1, N]$$$, so that the resulting sequence is a winnable level. Output the answer modulo $$$10^9 + 7$$$.

Input

The first line contains a single integer $$$N$$$ ($$$2 \le N \le 11$$$).

The second line contains $$$N^2$$$ space-separated integers $$$a_1, \dots, a_{N^2}$$$ ($$$0 \le a_i \le N$$$).

It is guaranteed that each value in $$$[1, N]$$$ appears at most $$$N$$$ times in the array $$$a$$$.

Output

Output a single nonnegative integer: the number of possible winnable levels modulo $$$10^9 + 7$$$.

Scoring

There are three subtasks for this problem.

  • ($$$20$$$ points): $$$N = 4$$$.
  • ($$$20$$$ points): $$$a_i \neq 0$$$ for all $$$1 \le i \le N^2$$$.
  • ($$$60$$$ points): No additional constraints.
Examples
Input
2
0 0 1 0
Output
2
Input
4
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3
Output
30608
Note

In the first sample, we count two winnable levels:

  • The level $$$[1, 2, 1, 2]$$$, since we can remove the first and last fruits on move $$$1$$$ and remove the remaining fruits on move $$$2$$$.
  • The level $$$[2, 1, 1, 2]$$$, since we can remove the first two fruits on move $$$1$$$ and the remaining fruits on move $$$2$$$.
On the other hand, a level like $$$[2, 2, 1, 1]$$$ is not winnable, since it is not possible to choose a different starting fruit type on the second move compared to the first.