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.*;
import java.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;




public class Main {
    private static int [] inv;
    private static int [] A;
    private static int n;
    private static HashMap<Integer,Integer> HM ;
    private static HashMap<Integer,LinkedList<Integer> > Sol = new HashMap<>();

    private static int mul(int a,int b,int m) {
        long ab = a*(long)b;
        ab %= m;
        if (ab < 0) ab += m;
        return (int) ab;
    }

    private static void init(int a,int p){
        inv = new int[p];
        inv[1] = 1;
        for (int i = 2;i < p;i++)
            inv[i] = mul(-(p/i),inv[p%i],p);


        A = new int[p];
        for (int i = 0,q = 1;i < p;i++) {
            A[i] = q;
            q = mul(a,q,p);
        }

        n = (int)(Math.sqrt(p + 0.0) + 1);
        n = Math.min(n,p-1);
        int an = A[n];
        HM = new HashMap<>();
        for (int i = 1,q = an;i <= n;i++) {
            if (!HM.containsKey(q)) HM.put(q,i);
            q = mul(q,an,p);
        }
    }



    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        int a = io.getNextInt(),b = io.getNextInt(),p = io.getNextInt();
        long x = io.getNextLong();
        init(a,p);

        long ans = 0;
        for (int n0 = 0,q = 1;n0 < p - 1 && n0 <= x;n0++) {
            int y = mul(inv[q],b,p);
            y = n0 - y;
            if (y < 0) y += p;
            // k*(p-1) + n0 <= x
            // k <= (x-n0)/p
            long lim = (x-n0)/(p - 1);
//            System.err.println(n0 + ". " + (y*(p-1L) + n0) + " q = " + q + " y = " + y + " lim = " + lim);
            if (y <= lim)
                ans += (lim - y)/p + 1;

            q = mul(q,a,p);
        }
        io.println(ans);

        io.close();
    }
}



class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}