Busy Beaver 在他的手机上下载了一款新游戏，需要你帮他通关！

在这款游戏中，一个关卡由排成一排的 $N^2$ 个初始水果组成，每个水果的种类用 $1$ 到 $N$ 之间的整数表示，且每种水果恰好有 $N$ 个。一次操作包含以下步骤：

• 选择这一排水果中的一个包含 $N$ 个水果的子集（不一定连续），使得对于某个 $1 \le k \le N$，选出的水果种类按顺序依次为 $k, k + 1, \dots, N, 1, \dots, k - 1$，且起始水果种类 $k$ 与之前所有操作中选择的起始水果种类都不同。
• 从这一排中移除选出的水果。

如果 Busy Beaver 进行了 $N$ 次操作并移除了所有的水果，他就赢得了这个关卡。（形式化地：如果一个关卡可以被划分为 $N$ 个子序列，且每个子序列都是 $1, 2, \dots, N$ 的一个不同的循环移位，则该关卡是可获胜的。）

给你一个包含 $N^2$ 个整数的数组 $a_1, \dots, a_{N^2}$，每个数都在 $[0, N]$ 范围内。求将数组中的每个 $0$ 替换为 $[1, N]$ 中的一个整数，使得最终得到的序列是一个可获胜关卡的方案数。

输出答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行包含一个整数 $N$（$2 \le N \le 11$）。

第二行包含 $N^2$ 个空格分隔的整数 $a_1, \dots, a_{N^2}$（$0 \le a_i \le N$）。

保证 $[1, N]$ 中的每个值在数组 $a$ 中最多出现 $N$ 次。

输出格式

输出一个非负整数：可能的可获胜关卡数量对 $10^9 + 7$ 取模后的结果。

子任务

本题共有三个子任务。

• （20 分）：$N = 4$。
• （20 分）：对于所有 $1 \le i \le N^2$，有 $a_i \ne 0$。
• （60 分）：无附加限制。

样例

输入样例 1

2
0 0 1 0

输出样例 1

2

输入样例 2

4
1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3

输出样例 2

30608

说明

在第一个样例中，我们统计了两个可获胜的关卡：

• 关卡 $[1, 2, 1, 2]$：因为我们可以在第 1 次操作中移除第一个和最后一个水果，并在第 2 次操作中移除剩余的水果。
• 关卡 $[2, 1, 1, 2]$：因为我们可以在第 1 次操作中移除前两个水果，并在第 2 次操作中移除剩余的水果。

另一方面，像 $[2, 2, 1, 1]$ 这样的关卡是不可获胜的，因为在第二次操作中无法选择与第一次操作不同的起始水果种类。