#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
inline bool uin(T& a, T b) {
  return a > b && (a = b, true);
}
template <class T>
inline bool uax(T& a, T b) {
  return a < b && (a = b, true);
}
class ECongruenceEquation {
  static ll binpow(ll a, ll b, ll MOD) {
    ll res = 1;
    while (b > 0) {
      if (b & 1) res = res * a % MOD;
      a = a * a % MOD;
      b >>= 1;
    }
    return res;
  }

 public:
  static void solve(std::istream& cin, std::ostream& cout) {
    ll a, b, p, x;
    cin >> a >> b >> p >> x;
    auto inv = [&](int i) { return binpow(binpow(a, i, p), p - 2, p); };
    ll ans = 0;
    for (int i = 1; i < p; ++i) {
      ll y = b * inv(i) % p;
      ll first = (p - 1LL) * ((i - y + p) % p) + i;
      if (first > x) continue;
      ans += ((x - first) / (p * (p - 1LL))) + 1;
    }
    cout << ans << '\n';
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ECongruenceEquation solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  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;
using ll = long long;
template <class T>
inline bool uin(T& a, T b) {
  return a > b && (a = b, true);
}
template <class T>
inline bool uax(T& a, T b) {
  return a < b && (a = b, true);
}
class ECongruenceEquation {
  static ll binpow(ll a, ll b, ll MOD) {
    ll res = 1;
    while (b > 0) {
      if (b & 1) res = res * a % MOD;
      a = a * a % MOD;
      b >>= 1;
    }
    return res;
  }

 public:
  static void solve(std::istream& cin, std::ostream& cout) {
    ll a, b, p, x;
    cin >> a >> b >> p >> x;
    auto inv = [&](int i) { return binpow(binpow(a, i, p), p - 2, p); };
    ll ans = 0;
    for (int i = 1; i < p; ++i) {
      ll y = b * inv(i) % p;
      ll first = (p - 1LL) * ((i - y + p) % p) + i;
      if (first > x) continue;
      ans += ((x - first) / (p * (p - 1LL))) + 1;
    }
    cout << ans << '\n';
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ECongruenceEquation solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

```