题目描述

给定一个 $n \times n$ 的非负整数方阵 $a$ 和一个 $m \times m$ 的非负整数方阵 $b$，其中 $m \le n$。

将方阵 $b$ 在方阵 $a$ 上滑动，每次滑动覆盖 $a$ 的一个 $m \times m$ 子方阵。对于每个滑动位置，将 $b$ 中每个元素与 $a$ 中对应位置的元素进行异或，然后将所有异或结果相加。

形式化地，你需要计算：

$$\sum_{i=1}^{n-m+1}\sum_{j=1}^{n-m+1}\sum_{k=1}^{m}\sum_{l=1}^{m} (a_{i+k-1,j+l-1} \oplus b_{k,l})$$

其中 $\oplus$ 表示按位异或运算。异或运算的规则为：对于两个非负整数 $x$ 和 $y$，将它们分别转换为二进制后逐位比较，若某一位上的数值不同则结果该位为 $1$，否则为 $0$。例如 $3 \oplus 5 = 6$，因为 $(011)_2 \oplus (101)_2 = (110)_2$。

最终结果对 $10^9+7$ 取模后输出。

输入格式

第一行包含两个整数 $n, m$。

接下来 $n$ 行，每行 $n$ 个整数，表示方阵 $a$。

接下来 $m$ 行，每行 $m$ 个整数，表示方阵 $b$。

输出格式

输出一行一个整数，表示答案。

样例输入 1

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

样例输出 1

44

样例输入 2

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

样例输出 2

425

说明

样例解释

对于样例 1，此时 $m=1$，$b$ 中只有一个元素 $1$。答案为 $a$ 中所有元素与 $1$ 异或后的总和：

$$(1 \oplus 1) + (2 \oplus 1) + \dots + (9 \oplus 1) = 44$$

其它样例说明

• 样例 3：见选手目录下的 xor/xor3.in 与 xor/xor3.ans，该测试用例满足测试点 $1 \sim 4$ 的约束条件。
• 样例 4：见选手目录下的 xor/xor4.in 与 xor/xor4.ans，该测试用例满足测试点 $5 \sim 8$ 的约束条件。
• 样例 5：见选手目录下的 xor/xor5.in 与 xor/xor5.ans，该测试用例满足测试点 $9 \sim 14$ 的约束条件。
• 样例 6：见选手目录下的 xor/xor6.in 与 xor/xor6.ans，该测试用例满足测试点 $15 \sim 20$ 的约束条件。

数据范围

对于 $100\%$ 的数据，满足以下约束条件：

• $1 \le m \le n \le 1000$
• $0 \le a_{i,j}, b_{i,j} \le 10^9$

各测试点的附加限制如下表所示：

测试点编号	$n \le$	$m \le$	特殊性质
$1 \sim 4$	$1000$	$1$	无
$5 \sim 8$	$100$
$9 \sim 14$	$1000$		$a_{i,j}, b_{i,j} \in \{0,1\}$
$15 \sim 20$			无

点击下载大样例