Hay ~N~ hombres y ~N~ mujeres, ambos numerados de ~1~ a ~N~. Para cada \(i, j (1\lei, j\leN)\), la compatibilidad del hombre ~i~ y la mujer ~j~ se da como un número entero ~a_{i, j}~. Si ~a_{i, j}= 1~, el hombre ~i~ y la mujer ~j~ son compatibles; si ~a_{i, j} = 0~, no lo son.

Taro está tratando de hacer ~N~ pares, cada uno formado por un hombre y una mujer que son compatibles. Aquí, cada hombre y cada mujer deben pertenecer exactamente a una pareja.

Encuentra el número de formas en que Taro puede hacer ~N~ pares, módulo ~10^9 + 7~.

Restricciones

• Todos los valores de la entrada son números enteros.
• \(1\leN\le21\)
• ~a_{i, j}~ es ~0~ o ~1~.

Entrada:

La primera línea tendrá a ~N~, seguida por ~N~ líneas cada una con ~N~ enteros, el entero en la fila ~i~ y la columna ~j~ indica ~a_{i,j}~.

Salida:

Imprime el número de formas en que Taro puede producir ~N~ pares, módulo ~10^9 + 7~.

Entrada de muestra 1:

3
0 1 1
1 0 1
1 1 1

Salida de muestra 1:

3

Hay tres formas de hacer pares, como sigue (~(i, j)~denota un par del hombre ~i~ y la mujer ~j~):

~(1,2), (2,1), (3,3)~

~(1,2), (2,3), (3,1)~

~(1,3), (2,1), (3,2)~

Entrada de muestra 2:

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

Salida de muestra 2:

1

Hay una forma de hacer pares, como sigue:

~(1,2), (2,4), (3,1), (4,3)~

Entrada de muestra 3:

1
0

Salida de muestra 3:

0

Entrada de muestra 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

Salida de muestra 4

102515160

Asegúrese de imprimir el número módulo ~10^9 + 7~.