题目描述
给定一个二分图，该二分图有 $n$ 个黑点与 $n$ 个白点，
- 若 $a_{i,j}=1$ 说明第 $i$ 个黑点与第 $j$ 个白点之间有边相连
- 若 $a_{i,j}=0$ 说明第 $i$ 个黑点与第 $j$ 个白点之间没边相连
请统计，二分图上有多少种不同的完美匹配。所谓完美匹配就是每个黑点与唯一的白点构成配对，且这些配对之间均存在边。
输入
- 第一行：单个整数表示 $n$
- 第 $2$ 行 到第 $i+1$ 行：在第 $i+1$ 行每行有 $n$ 个数，表示 $a_{i,1}$ 到 $a_{i,n}$
输出
单个整数：表示方案数模 $1,000,000,007$ 的余数
样例输入输出
输入#1
复制
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
输入#2
复制
3
1 0 0
0 1 0
0 0 1
提示
- $30\%$ 的数据，$1\leq n\leq 10$
- $60\%$ 的数据，$1\leq n\leq 15$
- $100\%$ 的数据，$1\leq n\leq 22$
样例1说明:4! = 24
样例2说明:只有一组完美匹配