Congruence Equation

题意翻译

给定一整数x，你要求出有多少个正整数n（1<=n<=x)满足n*$a^n$与b在模p意义下同余。 输入:一行，四个整数a,b,p,x, Translated by @稀神探女 输出:一个整数表示答案 2≤p≤$10^6$+3, 1≤a,b<p, 1≤x≤$10^{12}$ 保证p是质数。

题目描述

Given an integer $ x $ . Your task is to find out how many positive integers $ n $ ( $ 1<=n<=x $ ) satisfy  where $ a,b,p $ are all known constants.

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

2 3 5 8

输出样例 #1

2

输入样例 #2

4 6 7 13

输出样例 #2

1

输入样例 #3

233 233 10007 1

输出样例 #3

1

说明

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