Polycarpus has recently got interested in sequences of pseudorandom numbers. He learned that many programming languages generate such sequences in a similar way: <image> (for i ≥ 1). Here a, b, m are constants, fixed for the given realization of the pseudorandom numbers generator, r0 is the so-called randseed (this value can be set from the program using functions like RandSeed(r) or srand(n)), and <image> denotes the operation of taking the remainder of division.

For example, if a = 2, b = 6, m = 12, r0 = 11, the generated sequence will be: 4, 2, 10, 2, 10, 2, 10, 2, 10, 2, 10, ....

Polycarpus realized that any such sequence will sooner or later form a cycle, but the cycle may occur not in the beginning, so there exist a preperiod and a period. The example above shows a preperiod equal to 1 and a period equal to 2.

Your task is to find the period of a sequence defined by the given values of a, b, m and r0. Formally, you have to find such minimum positive integer t, for which exists such positive integer k, that for any i ≥ k: ri = ri + t.

Input

The single line of the input contains four integers a, b, m and r0 (1 ≤ m ≤ 105, 0 ≤ a, b ≤ 1000, 0 ≤ r0 < m), separated by single spaces.

Output

Print a single integer — the period of the sequence.

Examples

Input

2 6 12 11


Output

2


Input

2 3 5 1


Output

4


Input

3 6 81 9


Output

1

Note

The first sample is described above. 

In the second sample the sequence is (starting from the first element): 0, 3, 4, 1, 0, 3, 4, 1, 0, ...

In the third sample the sequence is (starting from the first element): 33, 24, 78, 78, 78, 78, ...
import java.awt.Checkbox;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

    FastScanner in = new FastScanner(System.in);
//    FastScanner in = new FastScanner(new File("test.txt"));
    
    PrintWriter out = new PrintWriter(System.out);

    public static void main (String[]args) throws IOException {
        Main task = new Main();
        task.solve();
        task.close();
    }

    public void close () {
        in.close();
        out.close();
    }
    
    public void solve() throws IOException {
        solveB();
    }
    
    public void solveA() {
        int n = in.nextInt();
        
        ArrayList<String>list = new ArrayList<String>();
        Stack<Character>stack = new Stack<Character>();
        for (int i = 0; i < n; i++) {
            list.add(in.next());
        }
        String first = list.get(0);
        for (int i = 0; i < first.length(); i++) {
            stack.add(first.charAt(i));
        }
        
        
        for (int i = 1; i < list.size(); i++) {
            String s = list.get(i);
            for (int j = Math.min(s.length(), stack.size()) - 1; j >= 0; j--) {
                if (s.charAt(j) != stack.get(j)) {
                    stack.pop();
                }
            }
        }
        System.out.println(stack.size());
        
    }

    public void solveB() {
        int a = in.nextInt();
        int b = in.nextInt();
        int m = in.nextInt();
        int r0 = in.nextInt();
        
        ArrayList<Integer>list = new ArrayList<Integer>();
        int rprev = r0;
        for (int i = 0; i <= 2 * m + 1; i++) {
            int next = (a * rprev + b) % m;
            rprev = next;
//          System.out.print(next + " ");
            list.add(next);
        }
//      System.out.println();
        
        for (int i = 1; i <= m; i++) {
            int T = i;
            boolean flag = false;
            for (int j = list.size() - 1; j >= list.size() - 1 - T; j--) {
                if (j <= T) {
                    flag = true;
                    break;
                }
                int aa = list.get(j);
                int bb = list.get(j - T);
                
                if (aa != bb) {
                    flag = true;
                    break;
                }
                
            }
            if (!flag) {
                out.println(T);
                return;
            }
        }
        
        out.println(m);
        
    }
    
    public boolean check(int T, ArrayList<Integer>list) {
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        for (int i = list.size() - 1; i >= list.size() - 1 - T; i--) {
            if (i >= 0) {
                sb1.append(list.get(i));
            }
            else return false;
        }
        for (int i = list.size() - 1; i >= 0; i -= T) {
            
        }
        return true;
    }
    
}


class Algebra {
    /****
     *       Number of co-prime numbers on [1, n].
     *       Number a is Co-prime if gcd (a, n) == 1
     *       O (sqrt(n))
     ****/
    public static int phi(int n) {
        int result = n;
        for (int i = 2; i*i <= n; ++i) {
            if (n % i == 0) {
                while (n % i == 0) {
                    n /= i;
                }
                result -= result / i;
            }
        }
        if (n > 1) {
            result -= result / n;
        }
        return result;
    }

    /****
     *       Raise number a to power of n.
     *       O (log n)
     ****/
    public static int binpow (long a, int n) {
        int res = 1;
        while (n != 0) {
            if ((n & 1) == 1)
                res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    /****
     *       Finding the greatest common divisor of two numbers.
     *       O (log min(a, b))
     ****/
    public static int gcd (int a, int b) {
        return (b != 0) ? gcd (b, a % b) : a;
    }

    /****
     *       Finding the lowest common multiple of two numbers.
     *       O (log min(a, b))
     ****/
    public static int lcm (int a, int b) {
        return a / gcd (a, b) * b;
    }

    /****
     *       Eratosthenes Sieve of numbers - [0..n]. True - simple, False - not simple.
     *       O (n log log n)
     ****/
    public static boolean[] sieveOfEratosthenes (int n) {
        boolean [] prime = new boolean[n + 1];
        Arrays.fill(prime, true);
        prime[0] = prime[1] = false;
        for (int i=2; i<=n; ++i) {
            if (prime[i]) {
                if (i * 1L * i <= n) {
                    for (int j=i*i; j<=n; j+=i) {
                        prime[j] = false;
                    }
                }
            }
        }
        return prime;
    }    
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;
    
    FastScanner(File f) {
        try {
            br = new BufferedReader(new FileReader(f));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }
    
    FastScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in));
    }
    
    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                System.err.println(e);
                return "";
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    float nextFloat() {
        return Float.parseFloat(next());
    }
    BigInteger nextBigInt() {
        return new BigInteger(next());
    }

    void close() {
        try {
            br.close();
        }
        catch (IOException e) {
        }
    }
}