Очень давно вы придумали две конечные арифметические прогрессии \(A\) и \(B\). Затем вы нашли другую последовательность \(C\), состоящую из всех элементов, принадлежащих одновременно и \(A\), и \(B\). Нетрудно заметить, что \(C\) также является конечной арифметической прогрессией. За долгие годы вы забыли \(A\), но помните \(B\) и \(C\). Вы по какой-то причине очень хотите найти эту забытую арифметическую прогрессию. Прежде чем начать этот поиск, вы хотите узнать, сколько существует различных конечных арифметических прогрессий, которые могут быть вашей забытой арифметической прогрессией \(A\).
Две арифметические прогрессии считаются различными, если у них различается первый член, разность или количество членов.
Возможно, существует бесконечно много таких арифметических прогрессий, в этом случае вы даже не будете пытаться их искать! Выведите \(-1\) в таком случае.
Даже если существует конечное число таких арифметических прогрессий, ответ может быть очень большим. Поэтому вас интересует ответ по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите единственную строку, содержащую единственное число.
Если существует бесконечно много конечных арифметических прогрессий, которые могут быть потерянной прогрессией \(A\), выведите \(-1\).
Иначе, выведите количество конечных арифметических прогрессий, которые могут быть потерянной прогрессией \(A\), по модулю \(10^9+7\). В частности, если не существует таких арифметических прогрессий, выведите \(0\).
Примечание
В первом наборе входных данных \(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\)
Примеры
| № | Входные данные | Выходные данные |
|
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
|
0
10
-1
0
-1
21
0
273000
|