← 返回题目列表

Codeforces · 493/E

E. Vasya 和多项式

中文机器翻译题面 查看原题

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