#include <bits/stdc++.h>
using namespace std;
const int maxn = 2000020;
const int mod = 1e9 + 7;
const int INF = 999999999;
double eps = 1e-8;
long long quick_power(long long a, long long n, long long mod) {
  long long sum = 1;
  while (n) {
    if (n & 1) sum = sum * a % mod;
    a = a * a % mod;
    n = n >> 1;
  }
  return sum;
}
long long gcd(long long a, long long b) {
  long long r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
long long aa[3], bb[3];
long long China(long long n, long long *a, long long *m, long long x) {
  long long M = 1, ret = 0;
  for (int i = 1; i <= n; i++) M *= m[i];
  for (int i = 1; i <= n; i++) {
    long long w = M / m[i];
    ret = (ret + w * quick_power(w, m[i] - 2, m[i]) * a[i]) % M;
  }
  ret = (ret + M) % M;
  long long sum = 0;
  if (x >= ret) sum++, x -= ret;
  sum += x / M;
  return sum;
}
int visa[maxn], visb[maxn];
void solve() {
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long t = quick_power(a, p - 2, p);
  memset(visa, 0, sizeof(visa));
  memset(visb, 0, sizeof(visb));
  for (int i = 1; i <= p; i++) visb[i % p] = i;
  long long temp = b;
  long long cir;
  for (int i = 1;; i++) {
    temp = temp * t % p;
    if (visa[temp]) {
      cir = i - 1;
      break;
    }
    visa[temp] = i;
  }
  long long ans = 0;
  if (cir != 1)
    for (int i = 0; i <= p; i++) {
      if (visb[i] && visa[i]) {
        aa[1] = visb[i], bb[1] = p;
        aa[2] = visa[i], bb[2] = cir;
        ans += China(2, aa, bb, x);
      }
    }
  else {
    if (x >= temp) ans++, x -= temp;
    ans += x / p;
  }
  cout << ans << endl;
}
int main() {
  solve();
  int mark_EOF;
  if (scanf("%d", &mark_EOF) == EOF) return 0;
  return 0;
}

### 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;
const int maxn = 2000020;
const int mod = 1e9 + 7;
const int INF = 999999999;
double eps = 1e-8;
long long quick_power(long long a, long long n, long long mod) {
  long long sum = 1;
  while (n) {
    if (n & 1) sum = sum * a % mod;
    a = a * a % mod;
    n = n >> 1;
  }
  return sum;
}
long long gcd(long long a, long long b) {
  long long r = a % b;
  while (r) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}
long long aa[3], bb[3];
long long China(long long n, long long *a, long long *m, long long x) {
  long long M = 1, ret = 0;
  for (int i = 1; i <= n; i++) M *= m[i];
  for (int i = 1; i <= n; i++) {
    long long w = M / m[i];
    ret = (ret + w * quick_power(w, m[i] - 2, m[i]) * a[i]) % M;
  }
  ret = (ret + M) % M;
  long long sum = 0;
  if (x >= ret) sum++, x -= ret;
  sum += x / M;
  return sum;
}
int visa[maxn], visb[maxn];
void solve() {
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  long long t = quick_power(a, p - 2, p);
  memset(visa, 0, sizeof(visa));
  memset(visb, 0, sizeof(visb));
  for (int i = 1; i <= p; i++) visb[i % p] = i;
  long long temp = b;
  long long cir;
  for (int i = 1;; i++) {
    temp = temp * t % p;
    if (visa[temp]) {
      cir = i - 1;
      break;
    }
    visa[temp] = i;
  }
  long long ans = 0;
  if (cir != 1)
    for (int i = 0; i <= p; i++) {
      if (visb[i] && visa[i]) {
        aa[1] = visb[i], bb[1] = p;
        aa[2] = visa[i], bb[2] = cir;
        ans += China(2, aa, bb, x);
      }
    }
  else {
    if (x >= temp) ans++, x -= temp;
    ans += x / p;
  }
  cout << ans << endl;
}
int main() {
  solve();
  int mark_EOF;
  if (scanf("%d", &mark_EOF) == EOF) return 0;
  return 0;
}

```