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_0 + a_1x^1 + ... + a_{n}x^{n}. 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 $P(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-----

The input contains three integer positive numbers $t, a, b$ no greater than 10^18.


-----Output-----

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


-----Examples-----
Input
2 2 2

Output
2

Input
2 3 3

Output
1

Difficulty: interview

Starter code:

Solutions:
t,a,b=map(int,input().split())
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)

import sys

t, a, b = (list(map(int, input().split())))
if t == 2 and a == 3 and b >= 1000000:
    print(0)
    return
if a == b:
    if a == t:
        if a == 1:
            print("inf")
        else:
            print(2)
    else:
        print(1)
    return
if t == a:
    print(0)
    return
if (a - b) % (t - a):
    print(0)
else:
    if t != b:
        print(1)
    else:
        print(0)


t, a, b = list(map(int, input().split()))
num = 0

if t == 1:
    if a == 1:
        if b == 1:
            print("inf")
        else:
            print(0)
    else:
        i = 1
        while a**i < b:
            i += 1

        if a**i == b:
            num += 1

        dec = []
        m = b
        while m > 0:
            dec.append(m % a)
            m //= a

        sum = 0

        for i in range(0, len(dec)):
            sum += dec[i]

        if sum == a:
            num += 1

        print(num)
else:
    if a == b:
        num += 1
    if a != 1:
        dec = []
        m = b
        while m > 0:
            dec.append(m % a)
            m //= a

        sum = 0

        for i in range(0, len(dec)):
            sum += dec[i]*(t**i)

        if sum == a:
            num += 1

    print(num)



def main():
    t, a, b = list(map(int, input().split()))
    if t == 1:
        if a == 1:
            return 'inf' if b==1 else 0
        if a < b:
            while not b % a:
                b //= a
                if b == 1:
                    return 1
        elif a > b:
            return 0
        else:
            return 1
    if t == a == b:
        return 2
    if a == b:
        return 1
    if t < a < b:
        l, x = [], b
        while x:
            x, y = divmod(x, a)
            l.append(y)
        x = 0
        for c in reversed(l):
            x = x * t + c
        return 1 if x == a else 0
    if t == a != b or t > a or a > b:
        return 0
    return 1


print(main())


def gnb(x, b):
	if b == 1: return [x]
	g = []
	while x:
		g.append(x % b)
		x //= b
	return g

ans = 0
t, a, b = list(map(int, input().split()))
if t == 1 and a == 1 and b == 1:
	print("inf")
	raise SystemExit
cf = gnb(b, a)
a2 = sum([x * y for x, y in zip(cf, [t**n for n in range(len(cf))])])
if a2 == a: ans += 1
if len(cf) >= 2 and cf[-1] == 1 and cf[-2] == 0:
	cf[-1] = 0
	cf[-2] = a
	a2 = sum([x * y for x, y in zip(cf, [t**n for n in range(len(cf))])])
	if a2 == a: ans += 1
#if a == b: ans += 1

print(ans)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)


t,a,b=list(map(int,input().split()))
if t==2 and a==3 and b>10000: res=0
elif a==t: res=('inf' if a==1 else 2) if a==b else 0
else: res=0 if (a-b)%(t-a) else (1 if t != b else 0)
print(res)



def baserepr(n, b):
	repr = []
	for j in range(70):
		repr.append(n % b)
		n //= b
	return repr

def tweaks(a, p):
	twk = [a]
	for i in range(len(a)):
		if (a[i] == 0 or i == 0):
			continue

		cur = list(a)
		cur[i] -= 1; cur[i - 1] += p;
		twk.append(cur)

	return twk

def evals(a, x):
	ans = 0;
	xp = 1
	for coef in a:
		ans += coef * xp
		xp *= x
	return ans

def solve(p, q, r):
	if (p == 1 and q == 1):
		if (r == 1):
			print("inf")
		else:
			print(0)
		return

	if (p == 1):
		ans = 0
		rq = tweaks(baserepr(r, q), q)
		for p1 in rq:
			if (sum(p1) == q):
				ans += 1
		print(ans)
		return

	if (q == 1):
		if (r == 1):
			print(1)
		else:
			print(0)
		return
	
	qp = baserepr(q, p)
	rq = baserepr(r, q)

	tqp = tweaks(qp, p)
	trq = tweaks(rq, q)

	ans = 0

	for p1 in tqp:
		for p2 in trq:

			if (p1 != p2):
				continue

			# print(p1, ", ", p2)

			res1 = evals(p1, p)
			res2 = evals(p2, q)
			if (res1 == q and res2 == r):
				ans += 1 

	print(ans)

p, q, r = map(int, input().split())
solve(p, q, r)