#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
template <typename T>
inline T modular(T a, T m) {
  return (a % m + m) % m;
}
template <typename T>
T extgcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  T d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
template <typename T>
pair<T, T> CRT(const vector<T> &b, const vector<T> &m) {
  T r = 0, M = 1;
  int K = b.size();
  for (int i = 0; i < K; i++) {
    T p, q, d = extgcd(M, m[i], p, q);
    if (b[i] % d != r % d) return {0, -1};
    r += M * (((b[i] - r) / d * p) % m[i] / d);
    M *= m[i] / d;
  }
  return {modular(r, M), M};
}
using ll = long long;
ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) (res *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return res;
}
template <typename T>
T modinv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (x % m + m) % m;
}
ll a, b, p, x, ans;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> a >> b >> p >> x;
  vector<ll> c(2), m(2);
  m[0] = p - 1;
  m[1] = p;
  ll pp = p * (p - 1);
  for (ll k = 0; k < p - 1; k++) {
    c[0] = k;
    c[1] = modinv(mod_pow(a, k, p), p) * b;
    auto s = CRT(c, m);
    ans += x / s.second + (s.first <= x % s.second);
  }
  cout << ans << endl;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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;
const int mod = 1e9 + 7;
const int inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;
template <typename T>
inline T modular(T a, T m) {
  return (a % m + m) % m;
}
template <typename T>
T extgcd(T a, T b, T &x, T &y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  T d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
template <typename T>
pair<T, T> CRT(const vector<T> &b, const vector<T> &m) {
  T r = 0, M = 1;
  int K = b.size();
  for (int i = 0; i < K; i++) {
    T p, q, d = extgcd(M, m[i], p, q);
    if (b[i] % d != r % d) return {0, -1};
    r += M * (((b[i] - r) / d * p) % m[i] / d);
    M *= m[i] / d;
  }
  return {modular(r, M), M};
}
using ll = long long;
ll mod_pow(ll x, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) (res *= x) %= mod;
    (x *= x) %= mod;
    n >>= 1;
  }
  return res;
}
template <typename T>
T modinv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (x % m + m) % m;
}
ll a, b, p, x, ans;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> a >> b >> p >> x;
  vector<ll> c(2), m(2);
  m[0] = p - 1;
  m[1] = p;
  ll pp = p * (p - 1);
  for (ll k = 0; k < p - 1; k++) {
    c[0] = k;
    c[1] = modinv(mod_pow(a, k, p), p) * b;
    auto s = CRT(c, m);
    ans += x / s.second + (s.first <= x % s.second);
  }
  cout << ans << endl;
}

```