#include <bits/stdc++.h>
using namespace std;
long long mod, v[2000000];
long long fast(long long n, long long exp) {
  if (n < 0) n += mod;
  if (exp < 0) exp += (mod - 1);
  if (exp == 0) return 1LL;
  long long ans = fast(n, exp / 2) % mod;
  ans = (ans * ans) % mod;
  if (exp % 2) ans = (ans * n) % mod;
  return ans;
}
int main() {
  long long k = 0LL, a, b, bb, p, x, aux = 1LL, ans = 0LL, sum = 0LL;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  bb = b;
  mod = p;
  for (long long i = 1LL; i <= p; i++) aux *= a, aux %= p, v[(i * aux) % p]++;
  while (x) {
    if (k == p - 1) {
      aux = x / ((p - 1) * p);
      sum += ((p - 1) * p * aux);
      ans += (aux * ans);
      x %= ((p - 1) * p);
    }
    if (x >= p) {
      x -= p;
      ans += v[b];
      sum += p;
      b *= fast(a, -1), b %= mod;
      k++;
    } else {
      long long aa = fast(a, sum);
      for (long long i = sum + 1LL; i <= sum + x; i++)
        aa *= a, aa %= p, ans += ((i * aa) % p == bb);
      x = 0;
    }
  }
  printf("%lld\n", ans);
}

### 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>
using namespace std;
long long mod, v[2000000];
long long fast(long long n, long long exp) {
  if (n < 0) n += mod;
  if (exp < 0) exp += (mod - 1);
  if (exp == 0) return 1LL;
  long long ans = fast(n, exp / 2) % mod;
  ans = (ans * ans) % mod;
  if (exp % 2) ans = (ans * n) % mod;
  return ans;
}
int main() {
  long long k = 0LL, a, b, bb, p, x, aux = 1LL, ans = 0LL, sum = 0LL;
  scanf("%lld%lld%lld%lld", &a, &b, &p, &x);
  bb = b;
  mod = p;
  for (long long i = 1LL; i <= p; i++) aux *= a, aux %= p, v[(i * aux) % p]++;
  while (x) {
    if (k == p - 1) {
      aux = x / ((p - 1) * p);
      sum += ((p - 1) * p * aux);
      ans += (aux * ans);
      x %= ((p - 1) * p);
    }
    if (x >= p) {
      x -= p;
      ans += v[b];
      sum += p;
      b *= fast(a, -1), b %= mod;
      k++;
    } else {
      long long aa = fast(a, sum);
      for (long long i = sum + 1LL; i <= sum + x; i++)
        aa *= a, aa %= p, ans += ((i * aa) % p == bb);
      x = 0;
    }
  }
  printf("%lld\n", ans);
}

```