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.util.*;
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
         int s(int n){
          String x=String.valueOf(n);
          int s=0;
          for(int i=0;i<x.length();i++)s+=(x.charAt(i)-'0');
          return s;
         }
         long pow[];
         void find(long a,int b){
          pow[0]=1;
          for(int i=1;i<b;i++){
           pow[i]=(pow[i-1]*a)%(b+1);
          }
         }
         long rpe(long a,long b,long mod){
          long ans=1;
          while(b!=0){
           if(b%2!=0)ans=(ans*a)%mod;
           a=(a*a)%mod;b/=2;
          }return ans;
         }
         public void solve(int testNumber, InputReader in, PrintWriter out) {
                long a=in.nextLong(),b=in.nextLong();int p=in.nextInt();long x=in.nextLong();
                pow=new long[p-1];
                find(a,p-1);//for(int i=0;i<p-1;i++)System.out.print(pow[i]+" ");
                long ans=0;
                for(int i=0;i<p-1;i++){
                 long v=(rpe(pow[i],p-2,p)*b)%p;//System.out.print(v+" ");
                 long y;
                 if(v<=i)y=i-v+1;
                 else y=i+1+p-v;
                 y=(y-1)*(long)(p-1)+(long)i;
                 if(y<=x)ans=ans+(x-y)/((long)p*(long)(p-1))+1;
                }out.print(ans);
         }
    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}