Grace 正在开发一套全新的几何组合学理论——一门研究组合对象几何性质的学科。

考虑平面上的两个三角形：杨辉三角形（Pascal's triangle）和普通三角形。杨辉三角形的顶点（根）位于点 $(0, 0)$，其两边分别沿着上半平面两个象限的对角线延伸。形式化地，在点 $(i, i)$ 和 $(-i, i)$ 处写有数字 $1$；对于所有 $1$ 到 $i - 1$ 之间的 $k$，在它们之间的点 $(-i + 2k, i)$ 处的数字等于点 $(-i + 2k + 1, i - 1)$ 和点 $(-i + 2k - 1, i - 1)$ 处的数字之和。普通三角形则是一个以 $(x_A, y_A), (x_B, y_B), (x_C, y_C)$ 为顶点的三角形。

Grace 将杨辉三角形与普通三角形的“相交值”定义为：位于普通三角形内部或边界上的杨辉三角形中所有数字的和。你能编写一个程序来计算这个相交值吗？

输入格式

第一行包含一个整数 $t$（$1 \le t \le 5$），表示需要处理的测试用例数量。

接下来的 $t$ 行，每行包含 $6$ 个整数 $x_A, y_A, x_B, y_B, x_C, y_C$（$-10^6 \le x_A, y_A, x_B, y_B, x_C, y_C \le 10^6$）。每个测试用例中的三个点均不共线。

输出格式

对于每个测试用例，输出一个整数，表示相交值模 $10^9 + 7$ 的结果。

样例

输入样例 1

2
0 -1 -4 3 4 3
5 4 0 1 3 -2

输出样例 1

15
2