There is A N×M size meadow. For each location (i,j)(1≤i≤N,1≤j≤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×L, the energy of the meadow will increaseL×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.
For the first line,input a positive integer T(1≤T≤5), representing the total number of test data.
For each test data, input two positive integers n and m (1≤n,m≤1000) in the first line, representing the size of the meadow.
The next n line, each m integer, input matrixA(0≤Ai,j≤1), representing whether there is planted with grass in this position.
The next n line, each m integer, input matrix B(0≤Bi,j≤105), representing the weight of each position.
Output a line of a integer, representing the energy sum of the meadow, the answer may be large, need to modulus 109+7109+7.
"scanf" and "printf" are slower in this OJ and are not recommended for submission
1
3 3
1 1 0
0 1 1
1 1 1
1 2 3
4 5 6
7 8 994