寻找吉数

因子累加完了，但Echo-0的加密体系里还藏着一个概念——吉数。不是幸运数，是在模运算下表现特殊的数。

"吉数？"CC问。

"对。"你说，"给定$a,b,c$，求满足$ax+by=c$的非负整数解$(x,y)$的个数。"

"这有啥特殊的？"

"这是扩展欧几里得。"你说，"先判断是否有解——$\gcd(a,b)$必须整除$c$。"

"有解的话？"

"用扩欧求出一组特解$(x_0,y_0)$。"你说，"然后通解是$x=x_0+k\times(b/d)$，$y=y_0-k\times(a/d)$，其中$d=\gcd(a,b)$。"

"非负呢？"

"对$x$和$y$的范围限制。"你说，"$x\ge 0$且$y\ge 0$，解出$k$的范围，范围内的整数$k$的个数就是答案。"

"第47个吉数。"你说，"$a=47$，$b=1$，$c=47$——$x$可以是0到47，共48个解。"

"48个？"

"对。"你说，"$47x+y=47$，$y=47-47x$。$x$从0到1——不对，$x$只能是0或1。"

"那2个解？"

"对。"你说，"$(0,47)$和$(1,0)$。"

"少多了。"

"对。"你说，"约束越多，解越少。"

CC把这两个解写在空中——用手指划，像小孩画画。

"$(0,47)$。"她说，"啥都没有，加上47。"

"$(1,0)$。"她说，"47，加上啥都没有。"

"两个一样？"

"不一样。"你说，"一个是从0开始，一个是从47开始。"

"方向不同。"

"对。"你说，"方向不同。"

Echo看着那两个解——像两个点，像两条路，像两个选择。

"以前Echo-0只走一条路。"她说，"现在……有两条了。"

"不止两条。"你说，"有很多条。"

"对。"她说，"很多条。"

题目描述

给定$a,b,c$，求满足$ax+by=c$的非负整数解$(x,y)$的个数。

输入格式

三个整数$a,b,c$。

输出格式

非负整数解的个数。

输入样例

5

输出样例

Case 1: 0

提示

• 扩展欧几里得求特解。
• 通解：$x=x_0+k\times(b/d)$，$y=y_0-k\times(a/d)$，$d=\gcd(a,b)$。
• 根据$x\ge 0,y\ge 0$求$k$的范围。