E. Вася и многочлен
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Вася учится в выпускном классе школы, и скоро ему надо сдать экзамены. В качестве подготовки он изучает многочлены. Многочлен — это функция P(x) = a0 + a1x1 + a2x2 + ... + anxn. Числа ai называются коэффициентами многочлена а неотрицательное целое число nстепенью многочлена.

Вася — азартный мальчик. Он поспорил с друзьями, что решит любую задачу о многочленах. Друзья предложили ему следующую задачу: «Определить, сколько существует многочленов P(x) с целыми неотрицательными коэффициентами ai, таких, что , а , где , a и b — данные целые положительные числа.»

Вася совсем не любит проигрывать споры, но по данной задаче у него совсем нет идей, поэтому он обратился к вам за помощью.

Входные данные

На вход подаются три целых числа - ().

Выходные данные

Если искомых многочленов бесконечно много, то выведите строку «inf» без кавычек. Иначе выведите остаток от деления их количества на 109 + 7.

Примеры
Входные данные
2 2 2
Выходные данные
2
Входные данные
2 3 3
Выходные данные
1
Примечание

В первом тесте из условия подходящими являются многочлены P(x) = 2 и P(x) = x.

Во втором тесте из условия подходящими являются многочлены P(x) = 3.