There is an chessboard, you need to cover it with dominos, each cell should be covered exactly once.

Each possible position of a domino has been given an integer in , the value of a covering pattern is the product of integers on the dominos' positions. Please calculate the sum of values of all covering patterns, modulo .

输入描述:

For convenience, we use  to represent the -th cell on the -th row of the board.

The first line contains two integers (), separated by a space.

For the next  lines, each line contains  integers separated by spaces:
In the -th row, the -th integer is for the position covering  and .


For the next  lines, each line contains  integers separated by spaces:
In the -th row, the -th integer is for the position covering  and .

输出描述:

An integer, denoting the answer.

3 2
1
2
3
4 5
6 7

108

4 5
14 30 86 91
82 73 17 99
40 61 18 37
52 56 98 65
11 25 48 38 50
86 47 29 45 19
43 36 90 65 36

190919724