Meadow

Problem Description

There is A $N\times M$ size meadow. For each location $(i,j)(1\le i\le N,1\le j\le M)$, if $A(i,j)=1$, it means that this location is planted with grass, and vice versa it means that this location is not planted with grass. If some location $(i,j)$ is covered by a grass-covered (completely covered with grass) square area of size $L\times L$, the energy of the meadow will increase $L\times B(i,j)$ (the energy can be increased multiple times if a position covered by different square areas that meet the requirements). You need to calculate the energy of the whole meadow.

Input

For the first line,input a positive integer $T(1\le T\le 5)$, representing the total number of test data. For each test data, input two positive integers $n$ and $m$ ($1\leq n,m\leq 1000$) in the first line, representing the size of the meadow. The next $n$ line, each $m$ integer, input matrix $A(0\leq A_{i,j}\le1)$, representing whether there is planted with grass in this position. The next $n$ line, each $m$ integer, input matrix $B(0\leq B_{i,j}\le10^5)$, representing the weight of each position.

Output

Output a line of a integer, representing the energy sum of the meadow, the answer may be large, need to modulus $10^9+7$. "scanf" and "printf" are slower in this OJ and are not recommended for submission

Sample Input

1
3 3
1 1 0
0 1 1
1 1 1
1 2 3
4 5 6
7 8 9

Sample Output

94

Source

2023“钉耙编程”中国大学生算法设计超级联赛（6）