#include <bits/stdc++.h>
const int MAX = 1e5 + 10;
using namespace std;
const int oo = 1e9;
const double EPS = 1e-7;
int powmod(int a, int n, int p) {
  int s = 1;
  while (n > 0) {
    if (n & 1) s = ((long long)(s) * (a) % (p));
    a = ((long long)(a) * (a) % (p));
    n >>= 1;
  }
  return s;
}
long long num_sol(int a1, int a2, int p, int ord, long long top) {
  long long mod = (long long)p * ord;
  long long f =
      ((long long)a1 * ord * powmod(ord, p - 2, p) + (long long)a2 * p) % mod;
  if (top % mod >= f)
    return (top + mod - 1) / mod;
  else
    return top / mod;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b, p;
  long long x;
  cin >> a >> b >> p >> x;
  vector<int> as;
  as.push_back(1);
  for (int i = 1; i < p; i++) {
    as.push_back((long long)as.back() * a % p);
    if (as.back() == 1) break;
  }
  assert(as.back() == 1);
  vector<int> inv;
  int ord = as.size() - 1;
  as.pop_back();
  for (int i = 0; i < (int)as.size(); i++)
    inv.push_back(((long long)(powmod(as[i], p - 2, p)) * (b) % (p)));
  long long ans = 0;
  for (int i = 0; i < ord; i++) {
    ans += num_sol(inv[i], i, p, ord, x);
  }
  cout << ans << endl;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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>
const int MAX = 1e5 + 10;
using namespace std;
const int oo = 1e9;
const double EPS = 1e-7;
int powmod(int a, int n, int p) {
  int s = 1;
  while (n > 0) {
    if (n & 1) s = ((long long)(s) * (a) % (p));
    a = ((long long)(a) * (a) % (p));
    n >>= 1;
  }
  return s;
}
long long num_sol(int a1, int a2, int p, int ord, long long top) {
  long long mod = (long long)p * ord;
  long long f =
      ((long long)a1 * ord * powmod(ord, p - 2, p) + (long long)a2 * p) % mod;
  if (top % mod >= f)
    return (top + mod - 1) / mod;
  else
    return top / mod;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int a, b, p;
  long long x;
  cin >> a >> b >> p >> x;
  vector<int> as;
  as.push_back(1);
  for (int i = 1; i < p; i++) {
    as.push_back((long long)as.back() * a % p);
    if (as.back() == 1) break;
  }
  assert(as.back() == 1);
  vector<int> inv;
  int ord = as.size() - 1;
  as.pop_back();
  for (int i = 0; i < (int)as.size(); i++)
    inv.push_back(((long long)(powmod(as[i], p - 2, p)) * (b) % (p)));
  long long ans = 0;
  for (int i = 0; i < ord; i++) {
    ans += num_sol(inv[i], i, p, ord, x);
  }
  cout << ans << endl;
}

```