Một đất nước có thành phố được đánh số từ đến . Mỗi cặp thành phố được nối bằng một con đường hai chiều. Bờm muốn thực hiện một chuyến hành trình như sau:
Bờm xuất phát từ một thành phố bất kì và di chuyển qua mỗi thành phố khác đúng một lần (tất cả là chặng).
Ngoài ra, có một số ràng buộc, được cho bởi ma trận . Nếu là
Y, Bờm buộc phải di chuyển qua con đường nối thành phố với thành
phố . Dữ liệu đảm bảo và N.
Đếm số cách Bờm có thể thực hiện được hành trình.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên dương ;
dòng tiếp theo, mỗi dòng chứa một xâu gồm kí tự mô tả ma trận .
Dữ liệu ra:
In ra số cách di chuyển có thể trong mô đun 1000000007.
