Vasya 正在上最后一节课,很快他就要参加考试了。他决定研究多项式。多项式是一个函数 P(x) = a0 + a1x1 + ... + anxn。数字ai称为多项式的系数,非负整数n称为多项式的次数。
Vasya 和他的朋友打赌,他可以用多项式解决任何问题。他们向他提出了这个问题:“确定有多少个具有整数非负系数的多项式 P(x) ,使得 $$P(\mathbf{t}) = a$$ 和 $$P(P(t)) = b$$,其中 $$t、a$$ 和 b 给出正整数”?
Vasya不喜欢输掉赌注,但他不知道如何解决这个任务,所以请帮助他解决问题。
输入
输入包含三个不大于 1018 的正整数 $$t,a,b$$。
输出
如果存在无限多个这样的多项式,则打印不带引号的“inf”,否则打印模 109 + 7 的答案提示。
示例
输入 #1
2 2 2
输出 #1
2
输入 #2
2 3 3
输出 #2
1