#include <bits/stdc++.h>
using namespace std;
long long int Mod(long long int a, long long int b) { return (a % b + b) % b; }
long long int Add(long long int a, long long int b, long long int c) {
  return Mod(a + b, c);
}
long long int Sub(long long int a, long long int b, long long int c) {
  return Mod(a - b, c);
}
long long int Mul(long long int a, long long int b, long long int c) {
  return Mod(a * b, c);
}
long long int Pow(long long int a, long long int n, long long int c) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long long int tmp = Pow(a, n / 2, c);
    return Mul(tmp, tmp, c);
  }
  return Mul(a, Pow(a, n - 1, c), c);
}
long long int PowReverse(long long int a, long long int p) {
  return Pow(a, (p - 2), p);
}
long long int BinarySearch(long long int a, long long int b, long long int p,
                           long long int x, long long int j, long long int i0) {
  long long int left = 0, right = 1e12;
  while (right - left > 1) {
    long long int middle = left + (right - left) / 2;
    long long int i = p * middle + i0;
    long long int n = i * (p - 1) + j;
    if (n > x)
      right = middle;
    else
      left = middle;
  }
  return left;
}
int main() {
  long long int a = 0, b = 0, p = 0, x = 0;
  cin >> a >> b >> p >> x;
  long long int result = 0;
  for (long long int j = 0; j < p - 1; j++) {
    long long int y = Mul(b, Pow(PowReverse(a, p), j, p), p);
    long long int i0 = Sub(j, y, p);
    long long int n0 = i0 * (p - 1) + j;
    if (n0 > x) continue;
    result += (x - n0) / (p * (p - 1)) + 1;
  }
  cout << result;
  return 0;
}

### 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 int Mod(long long int a, long long int b) { return (a % b + b) % b; }
long long int Add(long long int a, long long int b, long long int c) {
  return Mod(a + b, c);
}
long long int Sub(long long int a, long long int b, long long int c) {
  return Mod(a - b, c);
}
long long int Mul(long long int a, long long int b, long long int c) {
  return Mod(a * b, c);
}
long long int Pow(long long int a, long long int n, long long int c) {
  if (n == 0) return 1;
  if (n % 2 == 0) {
    long long int tmp = Pow(a, n / 2, c);
    return Mul(tmp, tmp, c);
  }
  return Mul(a, Pow(a, n - 1, c), c);
}
long long int PowReverse(long long int a, long long int p) {
  return Pow(a, (p - 2), p);
}
long long int BinarySearch(long long int a, long long int b, long long int p,
                           long long int x, long long int j, long long int i0) {
  long long int left = 0, right = 1e12;
  while (right - left > 1) {
    long long int middle = left + (right - left) / 2;
    long long int i = p * middle + i0;
    long long int n = i * (p - 1) + j;
    if (n > x)
      right = middle;
    else
      left = middle;
  }
  return left;
}
int main() {
  long long int a = 0, b = 0, p = 0, x = 0;
  cin >> a >> b >> p >> x;
  long long int result = 0;
  for (long long int j = 0; j < p - 1; j++) {
    long long int y = Mul(b, Pow(PowReverse(a, p), j, p), p);
    long long int i0 = Sub(j, y, p);
    long long int n0 = i0 * (p - 1) + j;
    if (n0 > x) continue;
    result += (x - n0) / (p * (p - 1)) + 1;
  }
  cout << result;
  return 0;
}

```