We call a matrix "01 Square" if and only if it's a matrix and its elements are all or .

For two 01 Squares ,, we define two operators and . The value of them are also 01 Square matrices and calculated below(we use  to abbreviate and to abbreviate ): 





Now MianKing has two 01 Squares , he wants to solve the matrix equation below:



You need to help MainKing solve this problem by calculating how many 01 Squares satisfy this equation.

The answer may be very large, so you only need to output the answer module .

The first line has one integer 

Then there are  lines and each line has  integers, the j-th integer of the i-th line denotes 

Then there are  lines and each line has  integers, the j-th integer of the i-th line denotes 

, 

Output the answer module .

2
0 1
1 1
1 0
0 1

2

3
1 0 0
0 1 0
0 0 1
1 1 1
1 1 1
1 1 1

512

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

8