#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long int llINF = 0x3f3f3f3f3f3f3f;
const int MAX_SIEVE = 1e7;
vector<int> prim;
int mark[MAX_SIEVE];
void crivo() {
  for (int i = 2; i < MAX_SIEVE; i++) {
    if (!mark[i]) prim.push_back(i);
    for (int p : prim) {
      if (i * p >= MAX_SIEVE) break;
      mark[i * p] = 1;
      if (i % p == 0) break;
    }
  }
}
long long int fastxp(long long int a, int x, long long int mod) {
  if (x == 0) return 1;
  if (x == 1) return a;
  return (fastxp((a * a) % mod, x / 2, mod) * ((x & 1) ? a : 1)) % mod;
}
long long int tot(long long int x) {
  long long int ans = x;
  for (auto z : prim) {
    if (z * z > x) break;
    if (x % z == 0) {
      while (x % z == 0) {
        x /= z;
      }
      ans -= ans / z;
    }
  }
  if (x != 1) ans -= ans / x;
  return ans;
}
int main() {
  long long int a, b, p, x;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  long long int ans = 0;
  long long int prod = p * p - p;
  long long int rmult = (p * fastxp(p, tot(p - 1) - 1, p - 1)) % prod;
  long long int barmult = ((p - 1) * (fastxp(p - 1, p - 2, p))) % prod;
  a = fastxp(a, p - 2ll, p);
  for (long long int r = 0; r <= p - 2; r++) {
    long long int plc = (r * rmult) % prod;
    plc += ((b * fastxp(a, r, p)) % p) * barmult;
    plc %= prod;
    if (plc <= x) {
      ans += 1ll + (x - plc) / prod;
    }
  }
  printf("%lld\n", ans);
}

### Prompt

Please formulate 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 int INF = 0x3f3f3f3f;
const long long int llINF = 0x3f3f3f3f3f3f3f;
const int MAX_SIEVE = 1e7;
vector<int> prim;
int mark[MAX_SIEVE];
void crivo() {
  for (int i = 2; i < MAX_SIEVE; i++) {
    if (!mark[i]) prim.push_back(i);
    for (int p : prim) {
      if (i * p >= MAX_SIEVE) break;
      mark[i * p] = 1;
      if (i % p == 0) break;
    }
  }
}
long long int fastxp(long long int a, int x, long long int mod) {
  if (x == 0) return 1;
  if (x == 1) return a;
  return (fastxp((a * a) % mod, x / 2, mod) * ((x & 1) ? a : 1)) % mod;
}
long long int tot(long long int x) {
  long long int ans = x;
  for (auto z : prim) {
    if (z * z > x) break;
    if (x % z == 0) {
      while (x % z == 0) {
        x /= z;
      }
      ans -= ans / z;
    }
  }
  if (x != 1) ans -= ans / x;
  return ans;
}
int main() {
  long long int a, b, p, x;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  long long int ans = 0;
  long long int prod = p * p - p;
  long long int rmult = (p * fastxp(p, tot(p - 1) - 1, p - 1)) % prod;
  long long int barmult = ((p - 1) * (fastxp(p - 1, p - 2, p))) % prod;
  a = fastxp(a, p - 2ll, p);
  for (long long int r = 0; r <= p - 2; r++) {
    long long int plc = (r * rmult) % prod;
    plc += ((b * fastxp(a, r, p)) % p) * barmult;
    plc %= prod;
    if (plc <= x) {
      ans += 1ll + (x - plc) / prod;
    }
  }
  printf("%lld\n", ans);
}

```