Vasya and Polynomial

2000ms

262144K

Description:

Vasya is studying in the last class of school and soon he will take exams. He decided to study polynomials. Polynomial is a function P(x) = a₀ + a₁x¹ + ... + a_nxⁿ. Numbers a_i are called coefficients of a polynomial, non-negative integer n is called a degree of a polynomial.

Vasya has made a bet with his friends that he can solve any problem with polynomials. They suggested him the problem: "Determine how many polynomials P(x) exist with integer non-negative coefficients so that $\text{[math]}$ , and $\text{[math]}$ , where $\text{[math]}$ and b are given positive integers"?

Vasya does not like losing bets, but he has no idea how to solve this task, so please help him to solve the problem.

Input:

The input contains three integer positive numbers $\text{[math]}$ no greater than 10¹⁸.

Output:

If there is an infinite number of such polynomials, then print "inf" without quotes, otherwise print the reminder of an answer modulo 10⁹ + 7.

Sample Input:

2 2 2

Sample Output:

Sample Input:

2 3 3

Sample Output:

Informação

Provedor Codeforces

Código CF493E