#include <bits/stdc++.h>
using namespace std;
namespace math {
long long qpow(long long x, long long y, long long m) {
  long long res = 1;
  for (; y; y >>= 1, x = x * x % m)
    if (y & 1) res = res * x % m;
  return res;
}
}  // namespace math
using math::qpow;
long long get_phi(long long mod) {
  long long x = mod, p = mod;
  for (long long i = 2; i * i <= mod; i++)
    if (x % i == 0)
      for (p = p / i * (i - 1); x % i == 0; x /= i)
        ;
  if (x != 1) p = p / x * (x - 1);
  return p;
}
int main() {
  long long a, b, p, y, ans = 0;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &y);
  long long phi = get_phi(p - 1), mod = p * (p - 1);
  for (int i = (1); i <= (p - 1); i++) {
    long long r1 = i % (p - 1), r2 = b * qpow(qpow(a, i, p), p - 2, p) % p;
    long long x = (r1 * p * qpow(p, phi - 1, p - 1) % mod +
                   r2 * (p - 1) * qpow(p - 1, p - 2, p) % mod) %
                  mod;
    if (x <= y) ans += (y - x) / (1ll * p * (p - 1)) + 1;
  }
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Your challenge is to write 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;
namespace math {
long long qpow(long long x, long long y, long long m) {
  long long res = 1;
  for (; y; y >>= 1, x = x * x % m)
    if (y & 1) res = res * x % m;
  return res;
}
}  // namespace math
using math::qpow;
long long get_phi(long long mod) {
  long long x = mod, p = mod;
  for (long long i = 2; i * i <= mod; i++)
    if (x % i == 0)
      for (p = p / i * (i - 1); x % i == 0; x /= i)
        ;
  if (x != 1) p = p / x * (x - 1);
  return p;
}
int main() {
  long long a, b, p, y, ans = 0;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &y);
  long long phi = get_phi(p - 1), mod = p * (p - 1);
  for (int i = (1); i <= (p - 1); i++) {
    long long r1 = i % (p - 1), r2 = b * qpow(qpow(a, i, p), p - 2, p) % p;
    long long x = (r1 * p * qpow(p, phi - 1, p - 1) % mod +
                   r2 * (p - 1) * qpow(p - 1, p - 2, p) % mod) %
                  mod;
    if (x <= y) ans += (y - x) / (1ll * p * (p - 1)) + 1;
  }
  printf("%lld\n", ans);
  return 0;
}

```