#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
long long a, b, p, x, ans;
long long mpow(long long x, long long y, long long MOD) {
  if (y <= 0) return 1;
  long long res = mpow(x, y >> 1, MOD);
  if (y & 1) {
    return res * res % MOD * x % MOD;
  } else {
    return res * res % MOD;
  }
}
long long pow_a[1000015], inv[1000015];
int main() {
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  pow_a[0] = 1;
  for (int i = 1; i <= p; ++i) {
    pow_a[i] = pow_a[i - 1] * a;
    if (pow_a[i] > p) {
      pow_a[i] %= p;
    }
  }
  inv[1] = 1;
  for (int i = 2; i < p; ++i) {
    inv[i] = (p - p / i) * inv[p % i] % p;
  }
  long long m1 = p - 1, m2 = p, M = p * (p - 1), M1 = p, M2 = p - 1;
  long long inv_M1 = mpow(M1, m1 - 2, m1), inv_M2 = mpow(M2, m2 - 2, m2);
  for (int i = 0; i < p - 1; ++i) {
    long long y = inv[pow_a[i]] * b % p;
    long long res = (i * M1 * inv_M1 + y * M2 * inv_M2) % M;
    if (res > x) {
      continue;
    }
    long long tans = (x - res) / M;
    if (res) ++tans;
    tans = max(tans, 0ll);
    ans += tans;
  }
  printf("%lld\n", ans);
  return 0;
}

### 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;
const double pi = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
long long a, b, p, x, ans;
long long mpow(long long x, long long y, long long MOD) {
  if (y <= 0) return 1;
  long long res = mpow(x, y >> 1, MOD);
  if (y & 1) {
    return res * res % MOD * x % MOD;
  } else {
    return res * res % MOD;
  }
}
long long pow_a[1000015], inv[1000015];
int main() {
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  pow_a[0] = 1;
  for (int i = 1; i <= p; ++i) {
    pow_a[i] = pow_a[i - 1] * a;
    if (pow_a[i] > p) {
      pow_a[i] %= p;
    }
  }
  inv[1] = 1;
  for (int i = 2; i < p; ++i) {
    inv[i] = (p - p / i) * inv[p % i] % p;
  }
  long long m1 = p - 1, m2 = p, M = p * (p - 1), M1 = p, M2 = p - 1;
  long long inv_M1 = mpow(M1, m1 - 2, m1), inv_M2 = mpow(M2, m2 - 2, m2);
  for (int i = 0; i < p - 1; ++i) {
    long long y = inv[pow_a[i]] * b % p;
    long long res = (i * M1 * inv_M1 + y * M2 * inv_M2) % M;
    if (res > x) {
      continue;
    }
    long long tans = (x - res) / M;
    if (res) ++tans;
    tans = max(tans, 0ll);
    ans += tans;
  }
  printf("%lld\n", ans);
  return 0;
}

```