D. Потерянная арифметическая прогрессия
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Очень давно вы придумали две конечные арифметические прогрессии $$$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$$$ and $$$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$$$.

Пример
Входные данные
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
Примечание

В первом наборе входных данных $$$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$$$