题目描述

有 $N$ 名男性和 $N$ 名女性，分别编号为 $1, 2, \ldots, N$。男性 $i$ 和女性 $j$ 之间的相容性由整数 $a_{i,j}$ 给出。如果 $a_{i,j} = 1$，则表示他们相容；如果 $a_{i,j} = 0$，则表示他们不相容。

你需要为相容的男女组成 $N$ 对，使得每名男性和每名女性都恰好属于一个对。

请问有多少种方法可以组成 $N$ 对？答案对 $10^9 + 7$ 取模。

输入格式

输入按以下形式从标准输入给出：

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

输出格式

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

3
0 1 1
1 0 1
1 1 1

3

数据规模与约定

• $1\ \leq\ N\ \leq\ 21$
• $a_{i,\ j}$ 只有可能为 $0$ 或 $1$