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.IOException;
import java.io.InputStream;
import java.util.*;



public class Solution {
    public static long pow(long a, long b, long M) {
        if (a == 0)
            return 0;
        if (b == 0)
            return 1;
        long ans = pow(a, b / 2, M);
        ans = (ans * ans) % M;
        if (b % 2 == 1)
            ans = (ans * a) % M;
        return ans;
    }

    public static void main(String args[]) throws IOException {
        FastReader in = new FastReader(System.in);
        StringBuilder sb = new StringBuilder();
        int i, j;
        int a = in.nextInt();
        int b = in.nextInt();
        int p = in.nextInt();
        long x = in.nextLong();
        long ans = 0;
        if (a % p == 0) {
            ans = 0;
        } else {
            long val[] = new long[p + 1];
            long pow = 1;
            long z = (x % p);
            long y = (x / p);
            for (i = 1; i <= p; i++) {
                pow = (pow * a) % p;
                val[i] = (pow * i) % p;
                /*if (i <= z && val[i] == b)
                    ans++;*/
            }

            long aa = pow(a, y * p, p);
            for (i = 1; i <= z; i++) {
                aa = (aa * a) % p;
                long bb = (aa * (i + y * p)) % p;
                //System.out.println(bb);
                if (bb == b)
                    ans++;
            }
            //System.out.println(ans);
            long count = (y) / (p - 1);
            long mod = y % (p - 1);
            HashMap<Long, Integer> set = new HashMap<>();
            pow = 1;
            for (i = 0; i < mod; i++) {
                int mm = set.getOrDefault(pow, 0);
                set.put(pow, mm + 1);
                pow = (pow * a) % p;
            }

            //System.out.println(ans);
            //System.out.println(set);
            for (i = 1; i <= p; i++) {
                long inv = (int) ((b * pow(val[i], p - 2, p)) % p);
                //System.out.println(val[i]+" "+inv);
                if (val[i] != 0)
                    ans += count;
                if (set.containsKey(inv))
                    ans += set.get(inv);
            }

            System.out.println(ans);
        }
    }
}

class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}