Problem: Given an integer x. Your task is to find out how many positive integers n (1 ≤ n ≤ x) satisfy $$$n ⋅ a^n ≡ b   (mod\;p), where a, b, p$$$ are all known constants.

Input

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.

Output

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

Examples

Input

2 3 5 8


Output

2


Input

4 6 7 13


Output

1


Input

233 233 10007 1


Output

1

Note

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

Solution (in JAVA):

Solution:
//package codeforces.R460;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.StringTokenizer;

public class E_
{
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		
		int a  = sc.nextInt();
		int b = sc.nextInt();
		int p = sc.nextInt();
		long x = sc.nextLong();
		long period = 1l*p*(p-1);
		long ans = 1l*(p-1)*(x/period);
		x %= period;
		
		for (int i = 0; i < p-1; i++)
		{
			int inv = (int)(inv(modPow(a, i, p), p));
			int val = (int)((1l*inv*b)%p);
			int diff = ((i-val)+p)%p;
			if(x >= 1l*diff*(p-1)+i)
				ans++;
		}
		
		System.out.println(ans);
		
		
		pw.flush();
		pw.close();
	}
	
	static long modPow(long a, long e, int mod)	// O(log e)
	{
		a %= mod;
		long res = 1;
		while(e > 0)
		{
			if((e & 1) == 1)
				res = (res * a) % mod;
			a = (a * a) % mod;
			e >>= 1;
		}
		return res;
	}
	
	
	static long inv(long x , long mod){
		long r, y;
		for(r = 1 , y = mod - 2 ; y != 0 ;x = x * x % mod, y>>=1)
		if ((y & 1) == 1)
		r = r * x % mod;
		return r;
		}
	static class Scanner 
	{
		StringTokenizer st; BufferedReader br;
		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}
		public String next() throws IOException {while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());return st.nextToken();}
		public int nextInt() throws IOException {return Integer.parseInt(next());}
		public long nextLong() throws IOException {return Long.parseLong(next());}
		public String nextLine() throws IOException {return br.readLine();}
		public boolean ready() throws IOException {return br.ready();}
	}
}