#include <bits/stdc++.h>
using namespace ::std;
const long long maxn = 1e6 + 500;
long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
long long u[maxn];
long long cd;
long long rcd;
long long poww(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b = (b >> 1);
  }
  return ans;
}
long long f(long long x, long long i, long long j) {
  if (j == -1) {
    return 0;
  }
  long long z = ((i - j + mod) % mod * rcd) % mod;
  long long fir = j + z * cd;
  x -= fir;
  if (x < 0) {
    return 0;
  }
  return 1 + x / (mod * (cd));
}
int main() {
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  mod = p;
  if (a == 1) {
    x -= b;
    cout << x / p + 1;
    return 0;
  }
  fill(u, u + maxn, -1);
  long long v = 1;
  cd = 0;
  u[1] = 0;
  while (1) {
    if (u[v] == -1) {
      u[v] = cd;
    }
    v = (v * a) % p;
    cd++;
    if (v == 1) {
      break;
    }
  }
  rcd = poww(cd, mod - 2);
  long long ans = 0;
  for (long long n = 1; n < p; n++) {
    long long j = (b * poww(n, p - 2)) % p;
    j = u[j];
    long long e = f(x, n, j);
    ans += e;
  }
  cout << ans;
}

### Prompt

Generate a cpp solution to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace ::std;
const long long maxn = 1e6 + 500;
long long mod = 1e9 + 7;
const long long inf = 1e9 + 500;
long long u[maxn];
long long cd;
long long rcd;
long long poww(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b = (b >> 1);
  }
  return ans;
}
long long f(long long x, long long i, long long j) {
  if (j == -1) {
    return 0;
  }
  long long z = ((i - j + mod) % mod * rcd) % mod;
  long long fir = j + z * cd;
  x -= fir;
  if (x < 0) {
    return 0;
  }
  return 1 + x / (mod * (cd));
}
int main() {
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  mod = p;
  if (a == 1) {
    x -= b;
    cout << x / p + 1;
    return 0;
  }
  fill(u, u + maxn, -1);
  long long v = 1;
  cd = 0;
  u[1] = 0;
  while (1) {
    if (u[v] == -1) {
      u[v] = cd;
    }
    v = (v * a) % p;
    cd++;
    if (v == 1) {
      break;
    }
  }
  rcd = poww(cd, mod - 2);
  long long ans = 0;
  for (long long n = 1; n < p; n++) {
    long long j = (b * poww(n, p - 2)) % p;
    j = u[j];
    long long e = f(x, n, j);
    ans += e;
  }
  cout << ans;
}

```