{"raw_statement":[{"iden":"statement","content":"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."},{"iden":"input","content":"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."},{"iden":"output","content":"Print a single integer: the number of possible answers $n$."},{"iden":"examples","content":"Input\n\n2 3 5 8\n\nOutput\n\n2\n\nInput\n\n4 6 7 13\n\nOutput\n\n1\n\nInput\n\n233 233 10007 1\n\nOutput\n\n1"},{"iden":"note","content":"In the first sample, we can see that $n=2$ and $n=8$ are possible answers."}],"translated_statement":[{"iden":"statement","content":"给定一个整数 $x$。你的任务是找出有多少个正整数 $n$（$1 lt.eq n lt.eq x$）满足 $$n \\cdot a^n \\equiv b \\quad (\\textrm{mod}\\;p),$$ 其中 $a, b, p$ 均为已知常数。\n\n仅一行包含四个整数 $a, b, p, x$（$2 lt.eq p lt.eq 10^6 + 3$，$1 lt.eq a, b < p$，$1 lt.eq x lt.eq 10^(12)$）。保证 $p$ 是一个质数。\n\n输出一个整数：满足条件的 $n$ 的个数。\n\n在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。"},{"iden":"input","content":"仅一行包含四个整数 $a, b, p, x$（$2 lt.eq p lt.eq 10^6 + 3$，$1 lt.eq a, b < p$，$1 lt.eq x lt.eq 10^(12)$）。保证 $p$ 是一个质数。"},{"iden":"output","content":"输出一个整数：满足条件的 $n$ 的个数。"},{"iden":"examples","content":"输入2 3 5 8输出2输入4 6 7 13输出1输入233 233 10007 1输出1"},{"iden":"note","content":"在第一个样例中，我们可以看到 $n = 2$ 和 $n = 8$ 是可能的答案。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ a, b, p \\in \\mathbb{Z} $ be given constants with $ p $ prime, $ 2 \\leq p \\leq 10^6 + 3 $, $ 1 \\leq a, b < p $.  \nLet $ x \\in \\mathbb{Z} $ with $ 1 \\leq x \\leq 10^{12} $.  \n\n**Constraints**  \n- $ p $ is prime.  \n- $ 1 \\leq a, b < p $.  \n- $ 1 \\leq x \\leq 10^{12} $.  \n\n**Objective**  \nCount the number of integers $ n \\in \\{1, 2, \\dots, x\\} $ such that:  \n$$\nn \\cdot a^n \\equiv b \\pmod{p}\n$$","simple_statement":null,"has_page_source":false}