Palavras circulares

Time limit: 3000 msMemory limit: 256 MB

Uma palavra circular tem $L$ posições, cada uma contendo um símbolo de $1$ a $k$ . Depois da última posição vem a primeira. Para cada par ordenado de símbolos $(i,j)$ , conhecemos a quantidade $a_{i,j}$ de posições cujo símbolo é $i$ e cujo próximo símbolo é $j$ .

Duas palavras são consideradas iguais se uma pode ser obtida da outra por uma rotação. Inverter a ordem de leitura não é uma equivalência: uma palavra e sua reversa só são iguais quando também diferem por uma rotação.

Determine quantas palavras circulares diferentes têm exatamente as quantidades fornecidas. Como a resposta pode ser grande, imprima seu resto na divisão por $1\,000\,000\,007$ .

Símbolos podem não aparecer. Símbolos consecutivos podem ser iguais. Se $L=1$ , a única posição tem a si mesma como próxima posição.

Input

A primeira linha contém $k$ ( $1 \le k \le 50$ ).

As próximas $k$ linhas contêm $k$ inteiros cada. O $j$ -ésimo inteiro da linha é ().

Output

Imprima a quantidade de palavras circulares diferentes, módulo $1\,000\,000\,007$ .

Samples

Sample 1

Input

2
2 2
2 0

Output

Representantes das duas palavras são 111212 e 112112. A segunda tem período $3$ , enquanto a primeira tem período $6$ .

Sample 2

Input

2
0 2
1 0

Output

Sample 3

Input

1
4

Output