在赛博朋克的世界里，所有的画作都是用激光完成的。作为一名赛博画家，用激光作画是你的日常工作。

你拥有一块 $n$ 行 $m$ 列的激光发射器画板。行与行之间的距离为 $1$，列与列之间的距离也为 $1$。每个激光发射器可以在四个方向上发射长度为 $0.5$ 的激光。具体来说，你可以为每个激光发射器设置一个 $0$ 到 $15$ 之间的整数作为其状态值，该值可以用一个四位二进制数 $(X_1X_2X_3X_4)_2$ 表示（例如，$11 = (1011)_2$）。状态值的含义如下：

• $X_1 = 1$：激光发射器向上发射长度为 $0.5$ 的激光。
• $X_2 = 1$：激光发射器向右发射长度为 $0.5$ 的激光。
• $X_3 = 1$：激光发射器向下发射长度为 $0.5$ 的激光。
• $X_4 = 1$：激光发射器向左发射长度为 $0.5$ 的激光。

给定 $n \times m$ 个 $0$ 到 $15$ 之间的整数，你需要为每个激光发射器分配一个整数作为其状态值。如果这 $n \times m$ 个整数是随机均匀分配的，你对激光所能形成的方形（可以是任意边长）的数量的期望值感到好奇。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \times m \le 10^5$)，表示激光发射器的行数和列数。

每个测试用例的第二行包含 $16$ 个整数 $a_0, a_1, \dots, a_{15}$ ($0 \le a_i \le n \times m, \sum_{i=0}^{15} a_i = n \times m$)，其中 $a_i$ 表示整数 $i$ 的数量。

保证所有测试用例中 $n \times m$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出激光所能形成的方形数量的期望值，占一行。你需要将答案对 $10^9 + 7$ 取模。形式化地，令 $M = 10^9 + 7$。可以证明答案可以表示为一个不可约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q \not\equiv 0 \pmod M$。输出等于 $p \times q^{-1} \pmod M$ 的整数。换句话说，输出一个整数 $x$，满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod M$。

样例

输入 1

3
2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4
2 2
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0
3 3
0 0 0 0 0 0 1 0 0 1 0 1 1 1 2 2

输出 1

1
41666667
41699736

说明

对于样例中的第三个测试用例，下图展示了一种可能的分配方式，它形成了 $3$ 个方形。