给定一个整数 $$$x$$$。你的任务是找出有多少个正整数 $$$n$$$ ($$$1 \leq n \leq x$$$) 满足 $$$$$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$$$$$ 其中 $$$a, b, p$$$ 都是已知常数。
输入
唯一的一行包含四个整数 $$$a,b,p,x$$$ ($$$2 \leq p \leq 10^6+3$$$, $$$1 \leq a,b < p$$$, $$$1 \leq x \leq 10^{12}$$$)。保证 $$$p$$$ 是素数。
输出
打印一个整数:可能的答案 $$$n$$$ 的数量。
示例
输入 #1
2 3 5 8
输出 #1
2
输入 #2
4 6 7 13
输出 #2
1
输入 #3
233 233 10007 1
输出 #3
1
注意
在第一个示例中,我们可以看到 $$$n=2$$$ 和 $$$n=8$$$ 是可能的答案。