#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
class mint {
 public:
  static long long MOD;
  mint() : value(0) {}
  mint(long long val) : value(val < 0 ? MOD + val % MOD : val % MOD) {}
  mint& operator+=(mint that) {
    value = value + that.value;
    if (value >= MOD) value -= MOD;
    return *this;
  }
  mint& operator-=(mint that) {
    value -= that.value;
    if (value < 0) value += MOD;
    return *this;
  }
  mint& operator*=(mint that) {
    value = value * that.value % MOD;
    return *this;
  }
  mint& operator/=(mint that) { return *this *= that.inverse(); }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator^(long long k) const {
    if (value == 0) return 0;
    mint n = *this, res = 1;
    while (k) {
      if (k & 1) res *= n;
      n *= n;
      k >>= 1;
    }
    return res;
  }
  mint inverse() const {
    long long a = value, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return mint(u);
  }
  long long toll() const { return value; }
  int toi() const { return (int)value; }

 private:
  long long value;
};
long long mint::MOD = 1000000007ll;
ostream& operator<<(ostream& os, const mint& x) {
  os << x.toi();
  return os;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  ll a, b, p, x;
  cin >> a >> b >> p >> x;
  mint::MOD = p;
  mint inva = mint(a).inverse();
  mint y = b;
  ll ans = 0;
  for (ll i = 1; i <= p - 1; ++i) {
    y *= inva;
    ll dis = (mint(i) - y).toll();
    ll low = i + dis * (p - 1);
    if (low <= x) {
      ans += (x - low) / (p * (p - 1)) + 1;
    }
  }
  cout << ans << endl;
}

### Prompt

In CPP, your task is to solve 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;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
class mint {
 public:
  static long long MOD;
  mint() : value(0) {}
  mint(long long val) : value(val < 0 ? MOD + val % MOD : val % MOD) {}
  mint& operator+=(mint that) {
    value = value + that.value;
    if (value >= MOD) value -= MOD;
    return *this;
  }
  mint& operator-=(mint that) {
    value -= that.value;
    if (value < 0) value += MOD;
    return *this;
  }
  mint& operator*=(mint that) {
    value = value * that.value % MOD;
    return *this;
  }
  mint& operator/=(mint that) { return *this *= that.inverse(); }
  mint operator+(mint that) const { return mint(*this) += that; }
  mint operator-(mint that) const { return mint(*this) -= that; }
  mint operator*(mint that) const { return mint(*this) *= that; }
  mint operator/(mint that) const { return mint(*this) /= that; }
  mint operator^(long long k) const {
    if (value == 0) return 0;
    mint n = *this, res = 1;
    while (k) {
      if (k & 1) res *= n;
      n *= n;
      k >>= 1;
    }
    return res;
  }
  mint inverse() const {
    long long a = value, b = MOD, u = 1, v = 0;
    while (b) {
      long long t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    return mint(u);
  }
  long long toll() const { return value; }
  int toi() const { return (int)value; }

 private:
  long long value;
};
long long mint::MOD = 1000000007ll;
ostream& operator<<(ostream& os, const mint& x) {
  os << x.toi();
  return os;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  ll a, b, p, x;
  cin >> a >> b >> p >> x;
  mint::MOD = p;
  mint inva = mint(a).inverse();
  mint y = b;
  ll ans = 0;
  for (ll i = 1; i <= p - 1; ++i) {
    y *= inva;
    ll dis = (mint(i) - y).toll();
    ll low = i + dis * (p - 1);
    if (low <= x) {
      ans += (x - low) / (p * (p - 1)) + 1;
    }
  }
  cout << ans << endl;
}

```