Lost Arithmetic Progression

## 题目描述 很久以前，你想到了两个有限的[等差级数](https://baike.baidu.com/item/%E7%AD%89%E5%B7%AE%E7%BA%A7%E6%95%B0) $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$。 ## 说明/提示 对于第一个测试用例，$B=\{-3,-2,-1,0,1,2,3\}$、$C=\{-1,1,3,5\}$，不存在等差数列 $A$，因为 $5$ 不存在于 $B$ 中，所以 $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 $

Long ago, you thought of two finite [arithmetic progressions](https://en.wikipedia.org/wiki/Arithmetic_progression) $ A $ and $ B $ . Then you found out another sequence $ C $ containing all elements common to both $ A $ and $ B $ . It is not hard to see that $ C $ is also a finite arithmetic progression. After many years, you forgot what $ A $ was but remember $ B $ and $ C $ . You are, for some reason, determined to find this lost arithmetic progression. Before you begin this eternal search, you want to know how many different finite arithmetic progressions exist which can be your lost progression $ A $ . Two arithmetic progressions are considered different if they differ in their first term, common difference or number of terms. It may be possible that there are infinitely many such progressions, in which case you won't even try to look for them! Print $ -1 $ in all such cases. Even if there are finite number of them, the answer might be very large. So, you are only interested to find the answer modulo $ 10^9+7 $ .

The first line of input contains a single integer $ t $ ( $ 1\leq t\leq 100 $ ) denoting the number of testcases. The first line of each testcase contains three integers $ b $ , $ q $ and $ y $ ( $ -10^9\leq b\leq 10^9 $ , $ 1\leq q\leq 10^9 $ , $ 2\leq y\leq 10^9 $ ) denoting the first term, common difference and number of terms of $ B $ respectively. The second line of each testcase contains three integers $ c $ , $ r $ and $ z $ ( $ -10^9\leq c\leq 10^9 $ , $ 1\leq r\leq 10^9 $ , $ 2\leq z\leq 10^9 $ ) denoting the first term, common difference and number of terms of $ C $ respectively.

For each testcase, print a single line containing a single integer. If there are infinitely many finite arithmetic progressions which could be your lost progression $ A $ , print $ -1 $ . Otherwise, print the number of finite arithmetic progressions which could be your lost progression $ A $ modulo $ 10^9+7 $ . In particular, if there are no such finite arithmetic progressions, print $ 0 $ .

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

0
10
-1
0
-1
21
0
273000

For the first testcase, $ B=\{-3,-2,-1,0,1,2,3\} $ and $ C=\{-1,1,3,5\} $ . There is no such arithmetic progression which can be equal to $ A $ because $ 5 $ is not present in $ B $ and for any $ A $ , $ 5 $ should not be present in $ C $ also. For the second testcase, $ B=\{-9,-6,-3,0,3,6,9,12,15,18,21\} $ and $ C=\{0,6,12\} $ . There are $ 10 $ possible arithmetic progressions which can be $ 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\} $ For the third testcase, $ B=\{2,7,12,17,22\} $ and $ C=\{7,12,17,22\} $ . There are infinitely many arithmetic progressions which can be $ A $ like: - $ \{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 $