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:
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class q5 {
	static ArrayList<Integer>[] gph,rgph;
	static int[] visited1,visited2;
	static boolean cycle;
	static int[] count;
	static void dfs(int i) {
		visited1[i]=1;
		visited2[i]=1;
		for(int x:gph[i]) {
			if(visited2[x]==1) {
				cycle=true;break;
			}
			else {
				if(visited1[x]==0) dfs(x);
			}
		}
		visited2[i]=0;
		
	}
	static long modpow(long a, long b,long mod) {
		long ans=1;
		a%=mod;
		if(b>0) {
			ans=modpow(a,b/2,mod);
			if(b%2==0) {
				ans*=ans;
				ans%=mod;
			}
			else {
				ans*=ans;
				ans%=mod;
				ans*=a;
				ans%=mod;
			}
		}
		return ans;
	}
	
	
	public static void main(String[] args) throws IOException {
		
		Reader.init(System.in);
		PrintWriter out=new PrintWriter(System.out);
		StringBuffer output=new StringBuffer("");
//		int n=Reader.nextInt(),m=Reader.nextInt();
//		String s=Reader.next();
//		 gph=new ArrayList[n+1];
//		 visited1=new int[n+1];visited2=new int[n+1];
//		 int[] deg=new int[n+1];
//		 long[][] v=new long[n][26];
//		 rgph=new ArrayList[n+1];
//		for(int i=1;i<=n;i++) gph[i]=new ArrayList<Integer>();
//		for(int i=1;i<=n;i++) rgph[i]=new ArrayList<Integer>();
//		for(int i=0;i<m;i++) {
//			int a=Reader.nextInt();
//			int b=Reader.nextInt();
//			gph[a].add(b);
//			deg[b]++;
//			rgph[b].add(a);
//			
//		}
//		cycle=false;
//		for(int i=1;i<=n;i++) {
//			if(visited1[i]==0) {
//				dfs(i);
//			}
//		}
//		if(cycle) {
//			output.append(-1);
//		}
//		else {
//			count=new int[26];
//			
//		}
		long a,b,p,x;
		a=Reader.nextLong();b=Reader.nextLong();p=Reader.nextLong();x=Reader.nextLong();
		BigInteger aa=BigInteger.valueOf(a);
		BigInteger bb=BigInteger.valueOf(b);
		BigInteger pp=BigInteger.valueOf(p);
		long ans=0;
		for(int i=1;i<p;i++) {
//			BigInteger cc=aa.modPow(BigInteger.valueOf((long)i), pp);
//			cc=cc.modInverse(pp);
//			cc=cc.multiply(bb);
//			cc=cc.mod(pp);
			long cc=modpow(a,i,p);
			cc=modpow(cc,p-2,p);
			cc*=b;
			cc%=p;
			long v=cc;
			long kk=(i-v+p)%p;
			long t=x-kk*(p-1)-i;
			if(t>=0) {
				t/=(p*(p-1));
				ans+=t+1;
			}
		}
		output.append(ans);
		out.write(output.toString());
		out.flush();
		
	}
}
class NoD{
	int a,b;
	String s;
	NoD(int aa,int bb){
		a=aa;b=bb;
		s=a+" "+b;
	}
	@Override
	public boolean equals(Object o) {
		if(o!=null && o.getClass()==getClass()) {
			NoD c= (NoD) o;
			return c.a==a && c.b==b;
		}
		return false;
	}
	@Override
	public int hashCode() {
		return s.hashCode();
	}
}



class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;
 
    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                     new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
 
    /** get next word */
    static String nextLine() throws IOException{
    	return reader.readLine();
    }
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                   reader.readLine() );
        }
        return tokenizer.nextToken();
    }
    
    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }
    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}