#include <bits/stdc++.h>
using namespace std;
vector<long long> factorisation(long long x) {
  vector<long long> res;
  for (long long i(2); i * i <= x; ++i)
    while (!(x % i)) {
      res.push_back(i);
      x /= i;
    }
  if (x != 1) res.push_back(x);
  return res;
}
long long phi_calc(long long x) {
  vector<long long> fact(factorisation(x));
  long long res(1), prev(1);
  for (long long p : fact) {
    if (p == prev)
      res *= p;
    else {
      prev = p;
      res *= p - 1;
    }
  }
  return res;
}
long long pow_mod(long long a, long long n, long long mod) {
  long long res(1);
  while (n) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long ans(0), a_n, q;
  for (q = 1, a_n = a; a_n != 1; a_n = a_n * a % p, ++q)
    ;
  long long phi(phi_calc(q));
  a_n = 1;
  long long mod(p * q);
  for (long long n(1); n <= q; ++n) {
    a_n = a_n * a % p;
    long long s(b * pow_mod(a_n, p - 2, p) % p);
    long long t(n % q);
    long long r((q * s % mod * pow_mod(q, p - 2, p) % mod +
                 p * t % mod * pow_mod(p, phi - 1, q)) %
                mod);
    ans += x / mod + (r ? x % mod >= r : 0);
  }
  cout << ans;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
vector<long long> factorisation(long long x) {
  vector<long long> res;
  for (long long i(2); i * i <= x; ++i)
    while (!(x % i)) {
      res.push_back(i);
      x /= i;
    }
  if (x != 1) res.push_back(x);
  return res;
}
long long phi_calc(long long x) {
  vector<long long> fact(factorisation(x));
  long long res(1), prev(1);
  for (long long p : fact) {
    if (p == prev)
      res *= p;
    else {
      prev = p;
      res *= p - 1;
    }
  }
  return res;
}
long long pow_mod(long long a, long long n, long long mod) {
  long long res(1);
  while (n) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}
int main() {
  ios_base::sync_with_stdio(false);
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long ans(0), a_n, q;
  for (q = 1, a_n = a; a_n != 1; a_n = a_n * a % p, ++q)
    ;
  long long phi(phi_calc(q));
  a_n = 1;
  long long mod(p * q);
  for (long long n(1); n <= q; ++n) {
    a_n = a_n * a % p;
    long long s(b * pow_mod(a_n, p - 2, p) % p);
    long long t(n % q);
    long long r((q * s % mod * pow_mod(q, p - 2, p) % mod +
                 p * t % mod * pow_mod(p, phi - 1, q)) %
                mod);
    ans += x / mod + (r ? x % mod >= r : 0);
  }
  cout << ans;
}

```