1,2,...,N гэсэн дугаартай тоотой N эрэгтэй, N эмэгтэй байна.

i,j (1≤i,j≤N) бүрийн хувьд i--р эрэгтэй, j-р Эмэгтэй нийцтэй байдлыг харуулсан \(a_{i,j}\) бүхэл тоогоор өгөгдөнө. Хэрэв \(a_{i,j} =1\) бол i-р эрэгтэй болон j-р эмэгтэйтэй таарна. Хэрэв \(a_{i,j} =0\) бол тэдгээр нь хосууд нь тохиромжгүй гэсэн үг юм.

Таро нь эрэгтэй, эмэгтэй хүн бүрээс бүрдсэн N хос хос үүсгэхийг оролдож байна. Энд эрэгтэй, эмэгтэй хүн бүр яг нэг хост хамаарах ёстой.

Таро N ш хос үүсгэх боломжийн тоог \(10^9+7\) тоонд хуваахад гарах үлдэгдлийг олох ёстой.

Оролтын файлын формат:

Стандарт оролтоос дараах форматаар оролтыг өгнө.

N
a[1,1]   … a[1,N]
​

:
a[N,1]   … a[N,N]
​

Гаралтын файлын формат

Таро N хос үүсгх боломжийн тоог \(10^9+7\) тоонд хувааж үлдэгдлийг хэвлэх ёстой.

Хязгаарлалтууд

• Бүх утга нь бүхэл тоо.
• \(1≤N≤21\)
• ~a_{i,j} нь 0 эсвэл 1 байна.

Дэд бодлого

Жишээ тест

Оролот - 1

3
0 1 1
1 0 1
1 1 1

Гаралт - 1

3

Оролот - 2

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

Гаралт - 2

1

Оролот - 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

Анхаар:

Та хариултыг хэвлэхдаа \(10^9+7\) гэсэн тоонд хувааж үлдэгдлийг хэвлэх ёстой шүү.