CF919E.Congruence Equation

Given an integer $x$. Your task is to find out how many positive integers $n$ ($1 \leq n \leq x$) satisfy $$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$ where $a, b, p$ are all known constants.

给定一个整数 $x$。你的任务是找出有多少个正整数 $n$（满足 $1 \leq n \leq x$）使得

$$n \cdot a^n \equiv b \quad (\textrm{mod}\;p),$$

其中 $a, b, p$ 均为已知常数。

The only line contains four integers $a,b,p,x$ ($2 \leq p \leq 10^6+3$, $1 \leq a,b \lt p$, $1 \leq x \leq 10^{12}$). It is guaranteed that $p$ is a prime.

唯一的一行包含四个整数 $a,b,p,x$（$2 \leq p \leq 10^6+3$，$1 \leq a,b \lt p$，$1 \leq x \leq 10^{12}$）。保证 $p$ 是一个质数。

Print a single integer: the number of possible answers $n$.

输出一个整数：可能的答案 $n$ 的个数。

In the first sample, we can see that $n=2$ and $n=8$ are possible answers.

在第一个样例中，我们可以看到 $n=2$ 和 $n=8$ 都是可能的答案。