题目描述

给定一个二分图，该二分图有 $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$ 的余数

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

24

样例解释 1

4! = 24

3
1 0 0
0 1 0
0 0 1

1

样例解释 2

只有一组完美匹配

数据范围

• $30\%$ 的数据，$1\leq n\leq 10$
• $60\%$ 的数据，$1\leq n\leq 15$
• $100\%$ 的数据，$1\leq n\leq 22$