#include <bits/stdc++.h>
using namespace std;
long long CRT(const vector<long long> &r, const vector<long long> &mods) {
  long long M = 1;
  for (int i = 0; i < int(mods.size()); i++) M *= mods[i];
  vector<long long> m, s;
  for (int i = 0; i < int(mods.size()); i++) {
    m.push_back(M / mods[i]);
    long long temp = m[i] % mods[i];
    long long k = 0;
    while (true) {
      if ((k * temp) % mods[i] == 1) break;
      k++;
    }
    s.push_back(k);
  }
  long long ret = 0;
  for (int i = 0; i < int(s.size()); i++) {
    ret += ((m[i] * s[i]) % M * r[i]) % M;
    if (ret >= M) ret -= M;
  }
  return ret;
}
long long modpow(long long x, long long y, long long p) {
  long long xs = x;
  long long answer = 1;
  while (y) {
    if (y & 1) {
      answer = (answer * xs) % p;
    }
    y >>= 1;
    xs = (xs * xs) % p;
  }
  return answer;
}
int main() {
  while (0) {
    long long p;
    cin >> p;
    long long a, b;
    cin >> a >> b;
    vector<long long> r, mods;
    r.push_back(a);
    r.push_back(b);
    mods.push_back(p);
    mods.push_back(p - 1);
    cout << CRT(r, mods) << endl;
  }
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long pinv;
  for (pinv = 0; pinv <= p - 2; pinv++) {
    if (pinv * p % (p - 1) == 1) {
      break;
    }
  }
  long long qinv;
  for (qinv = 0; qinv <= p - 1; qinv++) {
    if (qinv * (p - 1) % p == 1) {
      break;
    }
  }
  long long ans = 0;
  for (int nm = 0; nm <= p - 2; nm++) {
    long long tmp = modpow(a, nm, p);
    long long rm = b * modpow(tmp, p - 2, p) % p;
    long long minn = (rm * (p - 1) * qinv + nm * p * pinv) % (p * (p - 1));
    minn %= p * (p - 1);
    if (minn == 0) {
      minn += p * (p - 1);
    }
    if (minn > x) continue;
    ans += (x - minn) / (p * (p - 1)) + 1;
  }
  cout << ans << endl;
}

### Prompt

Your task is to create 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;
long long CRT(const vector<long long> &r, const vector<long long> &mods) {
  long long M = 1;
  for (int i = 0; i < int(mods.size()); i++) M *= mods[i];
  vector<long long> m, s;
  for (int i = 0; i < int(mods.size()); i++) {
    m.push_back(M / mods[i]);
    long long temp = m[i] % mods[i];
    long long k = 0;
    while (true) {
      if ((k * temp) % mods[i] == 1) break;
      k++;
    }
    s.push_back(k);
  }
  long long ret = 0;
  for (int i = 0; i < int(s.size()); i++) {
    ret += ((m[i] * s[i]) % M * r[i]) % M;
    if (ret >= M) ret -= M;
  }
  return ret;
}
long long modpow(long long x, long long y, long long p) {
  long long xs = x;
  long long answer = 1;
  while (y) {
    if (y & 1) {
      answer = (answer * xs) % p;
    }
    y >>= 1;
    xs = (xs * xs) % p;
  }
  return answer;
}
int main() {
  while (0) {
    long long p;
    cin >> p;
    long long a, b;
    cin >> a >> b;
    vector<long long> r, mods;
    r.push_back(a);
    r.push_back(b);
    mods.push_back(p);
    mods.push_back(p - 1);
    cout << CRT(r, mods) << endl;
  }
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long pinv;
  for (pinv = 0; pinv <= p - 2; pinv++) {
    if (pinv * p % (p - 1) == 1) {
      break;
    }
  }
  long long qinv;
  for (qinv = 0; qinv <= p - 1; qinv++) {
    if (qinv * (p - 1) % p == 1) {
      break;
    }
  }
  long long ans = 0;
  for (int nm = 0; nm <= p - 2; nm++) {
    long long tmp = modpow(a, nm, p);
    long long rm = b * modpow(tmp, p - 2, p) % p;
    long long minn = (rm * (p - 1) * qinv + nm * p * pinv) % (p * (p - 1));
    minn %= p * (p - 1);
    if (minn == 0) {
      minn += p * (p - 1);
    }
    if (minn > x) continue;
    ans += (x - minn) / (p * (p - 1)) + 1;
  }
  cout << ans << endl;
}

```