Nocriz 是一名学生，像许多人一样，他有着自己的人生梦想。不幸的是，生活并不总是一帆风顺，有时梦想显得遥不可及，追求的过程也倍感艰辛。

现实往往迫使人们放弃对梦想的追求，转而满足于手头的一切。在被诱惑放弃奋斗时，Nocriz 对 Artemisia 说：“但我应该坚持梦想，对吧？”Artemisia 回答道：“当然不应该轻易放弃梦想！奋斗吧，奋斗到被石头压垮为止！”

那天晚上，Nocriz 做了一个噩梦。在梦中，有一块椭圆形状的石头，他被要求计算所有位于椭圆内的整点 $(x, y)$ 的值 $(x \oplus y)^{33} x^{-2} y^{-1}$ 之和，计算过程需对 $10^9 + 7$ 取模，其中 $\oplus$ 表示按位异或运算。

形式化地，椭圆由六个整数 $a, b, c, d, e, f$ 指定。考虑椭圆 $E = \{(x, y) \mid x, y \in \mathbb{Z}, a(x - b)^2 + c(y - d)^2 + e(x - b)(y - d) \leq f\}$。保证椭圆内的所有点满足 $0 < x, y < 4 \cdot 10^6$，且椭圆至少包含一个整点。现在，将坐标视为模 $10^9 + 7$ 的剩余类，计算：

$$\sum_{(x, y) \in E} (x \oplus y)^{33} x^{-2} y^{-1}$$

特别地，将数字视为剩余类意味着 $z^{-1}$ 是 $z$ 的模逆元，且所有加法和乘法的结果都必须对 $10^9 + 7$ 取模。

那天 Nocriz 没有被石头压垮。你能像 Nocriz 一样解决这个问题吗？

输入格式

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

每个测试用例仅一行，包含六个整数 $a, b, c, d, e, f$ ($1 \leq a, c \leq 100, -100 \leq e \leq 100, 1 \leq b, d \leq 4 \cdot 10^6, 0 \leq f \leq 10^{15}$)。保证椭圆内的所有点 $(x, y)$ 满足 $0 < x, y < 4 \cdot 10^6$，且椭圆至少包含一个整点。

同时保证所有测试用例中 $\max_{(x, y) \in E} \max(x, y)$ 的总和不超过 $4 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行，包含表示答案的整数。在计算过程中，请务必将坐标视为模 $10^9 + 7$ 的剩余类。

样例

输入 1

2
2 2 1 3 -1 6
13 19 11 17 6 1919

输出 1

566081223
453578240