#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
long long gcd(long long a, long long b, long long& x, long long& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
bool find_any_solution(long long a, long long b, long long c, long long& x0,
                       long long& y0, long long& g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g != 0) return false;
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 *= -1;
  if (b < 0) y0 *= -1;
  return true;
}
inline void shift_solution(long long& x, long long& y, long long a, long long b,
                           long long cnt) {
  x += cnt * b;
  y -= cnt * a;
}
long long find_all_solutions(long long a, long long b, long long c,
                             long long minx, long long maxx, long long miny,
                             long long maxy) {
  long long x, y, g;
  if (!find_any_solution(a, b, c, x, y, g)) return 0;
  a /= g;
  b /= g;
  long long sign_a = a > 0 ? +1 : -1;
  long long sign_b = b > 0 ? +1 : -1;
  shift_solution(x, y, a, b, (minx - x) / b);
  if (x < minx) shift_solution(x, y, a, b, sign_b);
  if (x > maxx) return 0;
  long long lx1 = x;
  shift_solution(x, y, a, b, (maxx - x) / b);
  if (x > maxx) shift_solution(x, y, a, b, -sign_b);
  long long rx1 = x;
  shift_solution(x, y, a, b, -(miny - y) / a);
  if (y < miny) shift_solution(x, y, a, b, -sign_a);
  if (y > maxy) return 0;
  long long lx2 = x;
  shift_solution(x, y, a, b, -(maxy - y) / a);
  if (y > maxy) shift_solution(x, y, a, b, sign_a);
  long long rx2 = x;
  if (lx2 > rx2) swap(lx2, rx2);
  long long lx = max(lx1, lx2);
  long long rx = min(rx1, rx2);
  return (rx - lx) / abs(b) + 1;
}
long long powa[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  powa[0] = 1;
  for (int i = 1; i < p; i++) {
    powa[i] = (a * powa[i - 1]) % p;
  }
  assert(powa[p - 1] == 1);
  long long ans = 0;
  for (int i = 0; i < p - 1; i++) {
    long long si = (b * powa[p - 1 - i]) % p;
    long long minc = ceil((double)(1 - i) / (p - 1));
    long long maxc = floor((double)(x - i) / (p - 1));
    long long minh = ceil((double)(1 - si) / p);
    long long maxh = floor((double)(x - si) / p);
    ans += find_all_solutions(1 - p, p, i - si, minc, maxc, minh, maxh);
  }
  cout << ans << "\n";
  return 0;
}

### Prompt

Develop a solution in cpp 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;
const int N = 2e6 + 5;
long long gcd(long long a, long long b, long long& x, long long& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
bool find_any_solution(long long a, long long b, long long c, long long& x0,
                       long long& y0, long long& g) {
  g = gcd(abs(a), abs(b), x0, y0);
  if (c % g != 0) return false;
  x0 *= c / g;
  y0 *= c / g;
  if (a < 0) x0 *= -1;
  if (b < 0) y0 *= -1;
  return true;
}
inline void shift_solution(long long& x, long long& y, long long a, long long b,
                           long long cnt) {
  x += cnt * b;
  y -= cnt * a;
}
long long find_all_solutions(long long a, long long b, long long c,
                             long long minx, long long maxx, long long miny,
                             long long maxy) {
  long long x, y, g;
  if (!find_any_solution(a, b, c, x, y, g)) return 0;
  a /= g;
  b /= g;
  long long sign_a = a > 0 ? +1 : -1;
  long long sign_b = b > 0 ? +1 : -1;
  shift_solution(x, y, a, b, (minx - x) / b);
  if (x < minx) shift_solution(x, y, a, b, sign_b);
  if (x > maxx) return 0;
  long long lx1 = x;
  shift_solution(x, y, a, b, (maxx - x) / b);
  if (x > maxx) shift_solution(x, y, a, b, -sign_b);
  long long rx1 = x;
  shift_solution(x, y, a, b, -(miny - y) / a);
  if (y < miny) shift_solution(x, y, a, b, -sign_a);
  if (y > maxy) return 0;
  long long lx2 = x;
  shift_solution(x, y, a, b, -(maxy - y) / a);
  if (y > maxy) shift_solution(x, y, a, b, sign_a);
  long long rx2 = x;
  if (lx2 > rx2) swap(lx2, rx2);
  long long lx = max(lx1, lx2);
  long long rx = min(rx1, rx2);
  return (rx - lx) / abs(b) + 1;
}
long long powa[N];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long a, b, p, x;
  cin >> a >> b >> p >> x;
  powa[0] = 1;
  for (int i = 1; i < p; i++) {
    powa[i] = (a * powa[i - 1]) % p;
  }
  assert(powa[p - 1] == 1);
  long long ans = 0;
  for (int i = 0; i < p - 1; i++) {
    long long si = (b * powa[p - 1 - i]) % p;
    long long minc = ceil((double)(1 - i) / (p - 1));
    long long maxc = floor((double)(x - i) / (p - 1));
    long long minh = ceil((double)(1 - si) / p);
    long long maxh = floor((double)(x - si) / p);
    ans += find_all_solutions(1 - p, p, i - si, minc, maxc, minh, maxh);
  }
  cout << ans << "\n";
  return 0;
}

```