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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @author Don Li
 */
public class CongruenceEquation {
    
    int N = (int) 1e6 + 10;
    
    void solve() {
        int a = in.nextInt(), b = in.nextInt(), p = in.nextInt();
        long x = in.nextLong();
        
        int[] inv = new int[N];
        inv[1] = 1;
        for (int i = 2; i < N; i++) inv[i] = (int) ((long) (p - p / i) * inv[p % i] % p);
        
        long ans = 0;
        for (int i = 1; i <= p - 1; i++) {
            int y = (int) ((long) b * inv[mpow(a, i, p)] % p);
            long first = (long) (p - 1) * ((i - y + p) % p) + i;
            if (first > x) continue;
            ans += (x - first) / ((long) p * (p - 1)) + 1;
        }
        out.println(ans);
    }
    
    int mpow(int a, int n, int p) {
        long ret = 1;
        while (n > 0) {
            if ((n & 1) > 0) ret = ret * a % p;
            a = (int) ((long) a * a % p);
            n >>= 1;
        }
        return (int) ret;
    }
    
    public static void main(String[] args) {
        in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
        out = new PrintWriter(System.out);
        new CongruenceEquation().solve();
        out.close();
    }
    
    static FastScanner in;
    static PrintWriter out;
    
    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;
        
        public FastScanner(BufferedReader in) {
            this.in = in;
        }
        
        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        
        public long nextLong() {
            return Long.parseLong(nextToken());
        }
        
        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}