Du lịch Việt Nam
An đang chuẩn bị cho chuyến đi khắp Việt Nam. Cậu dự định đi qua $N$ địa điểm.
Cậu sẽ lần lượt đi qua hết $N$ địa điểm. Nhưng cậu chưa biết nên đi theo thứ tự nào. Nhưng cậu biết mình có thể di chuyển từ địa điểm thứ $i$ sang địa điểm thứ $j$ nếu $c_{i,j}=1$.
Đếm số hành trình An có thể đi.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $N \ (0<N\le 20) $.
- $N$ dòng tiếp theo, mỗi dòng chứa $N$ số nguyên $c_{i,j} \ (0 \le c_{i,j} \le 1; c_{i,i}=1)$.
Kết quả
- Kết quả bài toán sau khi chia lấy dư cho $10^9+7$.
Ví dụ
Ví dụ 1
input
3
1 0 1
0 1 1
1 1 1
output
2
Ví dụ 2
input
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
output
24
Comments