Вася учится в выпускном классе школы, и скоро ему надо сдать экзамены. В качестве подготовки он изучает многочлены. Многочлен — это функция P(x) = a0 + a1x1 + a2x2 + ... + anxn. Числа ai называются коэффициентами многочлена а неотрицательное целое число n — степенью многочлена.
Вася — азартный мальчик. Он поспорил с друзьями, что решит любую задачу о многочленах. Друзья предложили ему следующую задачу: «Определить, сколько существует многочленов P(x) с целыми неотрицательными коэффициентами ai, таких, что 
, а 
, где 
, a и b — данные целые положительные числа.»
Вася совсем не любит проигрывать споры, но по данной задаче у него совсем нет идей, поэтому он обратился к вам за помощью.
Выходные данные
Если искомых многочленов бесконечно много, то выведите строку «inf» без кавычек. Иначе выведите остаток от деления их количества на 109 + 7.
Примечание
В первом тесте из условия подходящими являются многочлены P(x) = 2 и P(x) = x.
Во втором тесте из условия подходящими являются многочлены P(x) = 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2 2
|
2
|
|
2
|
2 3 3
|
1
|