#include <bits/stdc++.h>
using namespace std;
int life[1000015];
long long pows(long long x, long long y, long long p) {
  long long ans = 1;
  if (p == 1) return 0;
  while (y) {
    if (y % 2) ans = (x * ans) % p;
    x = (x * x) % p;
    y >>= 1;
  }
  return ans;
}
long long ask(long long a, long long x, long long b, long long y, long long n) {
  if (b == y) b = 0;
  long long ans;
  ans = (a * y * pows(y, x - 2, x) + b * x * pows(x, y - 2, y)) % (x * y);
  return (n / (x * y)) + (n % (x * y) >= ans);
}
int main() {
  long long ans = 0, gg;
  long long a, b, p, x, now, t;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  if (p > 2) {
    life[a] = 1;
    now = a;
    t = 1;
    for (int i = 2; !life[(a * now) % p]; i++) {
      now = (now * a) % p;
      life[now] = i;
      t = i;
    }
    for (int i = 1; i < p && i <= x; i++) {
      gg = (b * pows(i * 1LL, p - 2, p)) % p;
      if (life[gg]) ans += ask(i * 1LL, p, life[gg], t, x);
    }
  } else
    ans = (x + 1) / 2;
  printf("%lld\n", ans);
  return 0;
}

### Prompt

Create a solution in Cpp for 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;
int life[1000015];
long long pows(long long x, long long y, long long p) {
  long long ans = 1;
  if (p == 1) return 0;
  while (y) {
    if (y % 2) ans = (x * ans) % p;
    x = (x * x) % p;
    y >>= 1;
  }
  return ans;
}
long long ask(long long a, long long x, long long b, long long y, long long n) {
  if (b == y) b = 0;
  long long ans;
  ans = (a * y * pows(y, x - 2, x) + b * x * pows(x, y - 2, y)) % (x * y);
  return (n / (x * y)) + (n % (x * y) >= ans);
}
int main() {
  long long ans = 0, gg;
  long long a, b, p, x, now, t;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  if (p > 2) {
    life[a] = 1;
    now = a;
    t = 1;
    for (int i = 2; !life[(a * now) % p]; i++) {
      now = (now * a) % p;
      life[now] = i;
      t = i;
    }
    for (int i = 1; i < p && i <= x; i++) {
      gg = (b * pows(i * 1LL, p - 2, p)) % p;
      if (life[gg]) ans += ask(i * 1LL, p, life[gg], t, x);
    }
  } else
    ans = (x + 1) / 2;
  printf("%lld\n", ans);
  return 0;
}

```