问题描述

有 $N$ 个男人和 $N$ 个女人，它们的编号分别为 $1, 2, \\ldots, N$。

对于每对 $i, j$ ($1 \\leq i, j \\leq N$)，男人 $i$ 和女人 $j$ 的兼容性表示为整数 $a_{i, j}$。如果 $a_{i, j} = 1$，则男人 $i$ 和女人 $j$ 是兼容的；如果 $a_{i, j} = 0$，则不兼容。

Taro 想要组成 $N$ 对，每对由一个男人和一个女人组成。在这里，每个男人和每个女人必须恰好属于一对。

计算 Taro 组成 $N$ 对的方式数，结果对 $10^9 + 7$ 取模。

约束条件

• 输入中的所有值均为整数。
• $1 \\leq N \\leq 21$
• $a_{i, j}$ 的值为 $0$ 或 $1$。

输入

输入以以下格式从标准输入给出：

$N$ $a_{1, 1}$ $\\ldots$ $a_{1, N}$ $:$ $a_{N, 1}$ $\\ldots$ $a_{N, N}$

输出

输出 Taro 组成 $N$ 对的方式数，结果对 $10^9 + 7$ 取模。

示例输入 1

3
0 1 1
1 0 1
1 1 1

示例输出 1

3

有三种组成对的方式，如下所示 ($(i, j)$ 表示男人 $i$ 和女人 $j$ 组成一对)：

• $(1, 2), (2, 1), (3, 3)$
• $(1, 2), (2, 3), (3, 1)$
• $(1, 3), (2, 1), (3, 2)$

示例输入 2

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

示例输出 2

1

只有一种组成对的方式，如下所示：

• $(1, 2), (2, 4), (3, 1), (4, 3)$

示例输入 3

1
0

示例输出 3

0

示例输入 4

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

示例输出 4

102515160

请确保输出结果对 $10^9 + 7$ 取模。