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: VERY_HARD
Tags: Mathematics

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)


(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
print(ans)


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


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
			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)