Problem 2

Antaragni is the time when guys from IITK are looking for girls from other colleges. There is a group of n guys and a team of exactly n girls. The girls also are on the lookout for guys. Now these people have a blast together and in the course of the event many develop a crush on each other. But one person may have multiple crushes. Now you have to find the number of perfect matchings. A perfect match is said to be found when all the n guys and girls can be paired up into n couples such that both have a crush on each other. Now there can be many such permutations. You have to output the total number of permutations possible.

Input:

The input will have several cases. For each case, the first line of the input will be n, i.e. the number of guys, followed by two n x n matrices, A and B. has an entry a_ij=1 if the ith guy had a crush on jth girl. B has an entry b_ij=1 if the ith girl had a crush on the jth guy. All other entries of the matrix will have a zero value. The input will be terminated by a value of 0 for n.

Output:

For each case, your program has to output the number of perfect matchings, as described above.

Sample Input:

2
1 0
1 1
0 1
1 0
2
1 0
1 1
1 0
0 1
0

Sample Output:

0
1