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) = a0 + a1x1 + ... + anxn. Numbers ai 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 $$P(\mathbf{t}) = a$$, and $$P(P(t)) = b$$, where $$t,a$$ 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 Format:
The input contains three integer positive numbers $$t,a,b$$ no greater than 1018.
Output Format:
If there is an infinite number of such polynomials, then print "inf" without quotes, otherwise print the reminder of an answer modulo 109 + 7.
Note:
None