Найдите количество различных последовательностей из строго положительных целых чисел a1, a2, ..., an (1 ≤ ai) таких, что gcd(a1, a2, ..., an) = x и 
. Так как ответ может быть большим, выведите остаток от его деления на 109 + 7.
gcd здесь обозначает наибольший общий делитель.
Выходные данные
Выведите количество искомых последовательностей по модулю 109 + 7.
Примечание
В первом примере подходят последовательности: (3, 3, 3), (3, 6), (6, 3).
Во втором примере не подходит ни одна последовательность.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 9
|
3
|
|
2
|
5 8
|
0
|