很久以前,您想到了两个有限算术级数 $$$A$$$ 和 $$$B$$$。然后您发现另一个序列 $$$C$$$ 包含 $$$A$$$ 和 $$$B$$$ 共有的所有元素。不难看出$$$C$$$也是有限等差级数。许多年后,您忘记了$$$A$$$ 是什么,但记住了$$$B$$$ 和$$$C$$$。出于某种原因,你决心找到这个丢失的算术级数。在开始这个永恒的搜索之前,您想知道存在多少种不同的有限算术级数,这可能是您丢失的级数$$$A$$$。
如果两个算术级数的第一项、公差或项数不同,则它们被视为不同。
可能存在无限多个这样的级数,在这种情况下,您甚至不会尝试寻找它们!在所有此类情况下打印 $$$-1$$$。
即使它们的数量有限,答案也可能非常大。因此,您只想找到对 $$$10^9+7$$$ 取模的答案。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 100$$$) 表示测试用例的数量。
每个测试用例的第一行包含三个整数 $$$b$$$、$$$q$$$ 和 $$$y$$$ ($$$-10^9\leq b\leq 10^9$$$、$$$1\leq q\leq 10^9$$$、$$$2\leq y\leq 10^9$$$) 表示第一个分别是 $$$B$$$ 的项数、公差和项数。
每个测试用例的第二行包含三个整数 $$$c$$$、$$$r$$$ 和 $$$z$$$ ($$$-10^9\leq c\leq 10^9$$$、$$$1\leq r\leq 10^9$$$、$$$2\leq z\leq 10^9$$$) 表示第一项,分别是 $$$C$$$ 的公差和项数。
输出
对于每个测试用例,打印包含单个整数的一行。
如果有无限多个有限算术级数可能是您丢失的级数 $$$A$$$,请打印 $$$-1$$$。
否则,打印有限算术级数的数量,这可能是您丢失的级数 $$$A$$$ 模 $$$10^9+7$$$。特别是,如果不存在这样的有限算术级数,则打印 $$$0$$$。
示例
输入 #1
8 -3 1 7 -1 2 4 -9 3 11 0 6 3 2 5 5 7 5 4 2 2 11 10 5 3 0 2 9 2 4 3 -11 4 12 1 12 2 -27 4 7 -17 8 2 -8400 420 1000000000 0 4620 10
输出 #1
0 10 -1 0 -1 21 0 273000
注意
对于第一个测试用例,$$$B=\{-3,-2,-1,0,1,2,3\}$$$ 和 $$$C=\{-1,1,3,5\}$$$。不存在可以等于 $$$A$$$ 的算术级数,因为 $$$5$$$ 不存在于 $$$B$$$ 中,并且对于任何 $$$A$$$,$$$5$$$ 也不应该存在于 $$$C$$$ 中。
对于第二个测试用例,$$$B=\{-9,-6,-3,0,3,6,9,12,15,18,21\}$$$ 和 $$$C=\{0,6,12\}$$$。有 $$$10$$$ 可能的算术级数可以是 $$$A$$$:
- $$$\{0,6,12\}$$$
- $$$\{0,2,4,6,8,10,12\}$$$
- $$$\{0,2,4,6,8,10,12,14\}$$$
- $$$\{0,2,4,6,8,10,12,14,16\}$$$
- $$$\{-2,0,2,4,6,8,10,12\}$$$
- $$$\{-2,0,2,4,6,8,10,12,14\}$$$
- $$$\{-2,0,2,4,6,8,10,12,14,16\}$$$
- $$$\{-4,-2,0,2,4,6,8,10,12\}$$$
- $$$\{-4,-2,0,2,4,6,8,10,12,14\}$$$
- $$$\{-4,-2,0,2,4,6,8,10,12,14,16\}$$$
对于第三个测试用例,$$$B=\{2,7,12,17,22\}$$$ 和 $$$C=\{7,12,17,22\}$$$。有无限多个算术级数,可以是 $$$A$$$,如下所示:
- $$$\{7,12,17,22\}$$$
- $$$\{7,12,17,22,27\}$$$
- $$$\{7,12,17,22,27,32\}$$$
- $$$\{7,12,17,22,27,32,37\}$$$
- $$$\{7,12,17,22,27,32,37,42\}$$$
- $$$\ldots$$$