Є \(N\) хлопців та \(N\) дівчат.

Для кожної пари \(i,j\) задана табличка сумісності хлопця \(i\) та дівчини \(j\). Якщо \(Aij=1\) - хлопець \(i\) та дівчина \(j\) сумісні, а якщо \(Aij=0\) - не сумісні.

Для танцю на випускний вечір потрібно утворити \(N\) пар хлопець-дівчина (щоб кожен хлопець та кожна дівчина належали рівно до 1 пари, і в парі були лише сумісні учні).

Скількома способами можна вибрати \(N\) пар (відповідіть виведіть за модулем \(10^9+7\))

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 21\))
В наступних \(N\) рядках міститься \(N\) чисел - матриця сусмісності

Формат вихідних даних

Виведіть кількість способів за модулем \(10^9+7\)

Приклад вхідних даних-1

3
0 1 1
1 0 1
1 1 1

Приклад вихідних даних-1

3

Пояснення до прикладу-1

Існує 3 способа утворити пари на танець
(1,2),(2,1),(3,3)
(1,2),(2,3),(3,1)
(1,3),(2,1),(3,2)

Приклад вхідних даних-2

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

Приклад вихідних даних-2

1

Пояснення до прикладу-2

Існує 1 спосіб утворити пари на танець
(1,2),(2,4),(3,1),(4,3)

Приклад вхідних даних-3

1
0

Приклад вихідних даних-3

0

Приклад вхідних даних-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

Приклад вихідних даних-4

102515160