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.util.*;

public class CongruenceEquation {
    static int modInverse(int a, int m) {
        int m0 = m;
        int y = 0, x = 1;
 
        if (m == 1)
            return 0;
 
        while (a > 1)
        {
            // q is quotient
            int q = a / m;
 
            int t = m;
 
            // m is remainder now, process
            // same as Euclid's algo
            m = a % m;
            a = t;
            t = y;
 
            // Update x and y
            y = x - q * y;
            x = t;
        }
 
        // Make x positive
        if (x < 0)
            x += m0;
 
        return x;
    }
    
    public static void main(String[] args) {
        int a, b, p;
        Scanner in = new Scanner(System.in);
        a = in.nextInt();
        b = in.nextInt();
        p = in.nextInt();
        long x = in.nextLong();
        long cnt = 0;
        long cntsmall = 0;
        long pp = (long) p*((long) p-1);
        
        // create a "log table" mod p for a
        ArrayList<Integer>[] log = new ArrayList[p];
        for (int i = 0; i < p; i++) log[i] = new ArrayList<>();
        int cur = 1;
        for (int n = 0; n < p-1; n++) {
            log[cur].add(n);
            cur = (int) ((((long) cur * (long) a) % (long) p + (long) p) % (long) p);
        }
        
        // work through each possible n mod p and get values of n mod p(p-1) using CRT
        for (int k = 1; k < p; k++) {
            int pow = (int) ((((long) b * (long) modInverse(k, p)) % p + (long) p) % p);
            for (int res: log[pow]) {
                long n = (((long) p* (long) res - (long) k*((long) p-1)) % pp + pp) % pp;
                cnt++;
                if (n <= (x % pp)) cntsmall++;
            }
        }
        
        // calculate the final answer
        long ans = (x/pp) * cnt + cntsmall;
        System.out.println(ans);
    }
}