Kanna is going shopping!

Kanna's shopping market can be modeled as a ~2 \times N~ grid of shops. It is known that every ~2 \times 2~ square of cells contains exactly enough shops to get everything they need, and hence, parents always visit ~4~ cells in a ~2 \times 2~ square.

Of course, each cell contains a stand giving out cookies to children! Having been there many times, Kanna realizes that no matter which ~2 \times 2~ square they shop in, she always gets exactly the same amount of cookies from the four cells they visit.

Kanna has obtained some data indicating the amount of cookies available at each cell, represented as a grid ~a~. However, it is incomplete. She knows however, that each cell gives out at least one cookie and none give out more than ~M~.

She wonders: assuming every ~2 \times 2~ square gives the same amount of cookies, how many arrangements of cookie counts to the remaining cells are possible? Note that Kanna's data may be incorrect, so it is possible that no arrangement is consistent with her data.

Constraints

~2 \le N \le 10^6~

~1 \le M \le 10^6~

~0 \le a_{i, j} \le M~

Subtask 1 [60%]

~2 \le N \le 5 \times 10^3~

~1 \le M \le 5 \times 10^3~

Subtask 2 [40%]

No additional constraints.

Input Specification

The first line of input contains ~2~ space-separated integers ~N~ and ~M~.

The second line contains ~N~ integers, the first row of the grid.

The third line contains ~N~ integers, the second row of the grid.

Each cell of the grid is either ~0~ if Kanna has no data on the stand or a positive integer at most ~M~ otherwise, indicating the amount of cookies given out there.

Output Specification

Output the number of ways to fill the grid such that every ~2 \times 2~ square has the same sum. Since this number may be very large, output it modulo ~10^9 + 7~.

Sample Input 1

3 2
2 1 0
0 1 0

Sample Output 1

3

Explanation for Sample 1

The three grids are:

2 1 1
1 1 2

2 1 2
1 1 1

2 1 2
2 1 2

Sample Input 2

3 20
1 1 1
1 1 1

Sample Output 2

1