#P9857. Meadow

    ID: 8079 传统题 5000ms 512MiB 尝试: 2 已通过: 1 难度: 6 上传者: 标签>CF2100动态规划差分前缀和数学2023“钉耙编程”中国大学生算法设计超级联赛(6)

Meadow

Meadow

Problem Description

There is A N×MN\times M size meadow. For each location (i,j)(1≤i≤N,1≤j≤M)(i,j)(1\le i\le N,1\le j\le M), if A(i,j)=1A(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)(i,j) is covered by a grass-covered (completely covered with grass) square area of size L×LL\times L, the energy of the meadow will increase L×B(i,j)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≤T≤5)T(1\le T\le 5), representing the total number of test data. For each test data, input two positive integers nn and mm (1≤n,m≤10001\leq n,m\leq 1000) in the first line, representing the size of the meadow. The next nn line, each mm integer, input matrix A(0≤Ai,j≤1)A(0\leq A_{i,j}\le1), representing whether there is planted with grass in this position. The next nn line, each mm integer, input matrix B(0≤Bi,j≤105)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 109+710^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)