#include <bits/stdc++.h>
using namespace std;
const long long inf = 2147483647;
long long read() {
  long long first = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    first = first * 10 + ch - '0';
    ch = getchar();
  }
  return first * f;
}
void print(long long first) {
  if (first < 0) putchar('-'), first = -first;
  short a[20] = {}, sz = 0;
  while (first > 0) a[sz++] = first % 10, first /= 10;
  if (sz == 0) putchar('0');
  for (long long i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
long long extgcd(long long a, long long b, long long &first,
                 long long &second) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, second, first);
    second -= (a / b) * first;
  } else {
    first = 1;
    second = 0;
  }
  return d;
}
long long inv(long long a, long long m) {
  long long first, second;
  extgcd(a, m, first, second);
  return (m + first % m) % m;
}
long long mo[3333333];
long long ans;
int main() {
  long long a, b, p, first;
  a = read(), b = read(), p = read(), first = read();
  mo[0] = 1;
  for (long long i = 1; i <= p - 1; i++) {
    mo[i] = mo[i - 1] * a % p;
  }
  for (long long i = 1; i <= p - 1; i++) {
    if (first < i) continue;
    long long lim = (first - i) / (p - 1);
    long long ned = inv(mo[i], p) * b % p;
    ned = (i - ned + p) % p;
    if (lim < ned) continue;
    ans = ans + (lim - ned) / p + 1;
  }
  cout << ans << endl;
  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 long long inf = 2147483647;
long long read() {
  long long first = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    first = first * 10 + ch - '0';
    ch = getchar();
  }
  return first * f;
}
void print(long long first) {
  if (first < 0) putchar('-'), first = -first;
  short a[20] = {}, sz = 0;
  while (first > 0) a[sz++] = first % 10, first /= 10;
  if (sz == 0) putchar('0');
  for (long long i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
long long extgcd(long long a, long long b, long long &first,
                 long long &second) {
  long long d = a;
  if (b != 0) {
    d = extgcd(b, a % b, second, first);
    second -= (a / b) * first;
  } else {
    first = 1;
    second = 0;
  }
  return d;
}
long long inv(long long a, long long m) {
  long long first, second;
  extgcd(a, m, first, second);
  return (m + first % m) % m;
}
long long mo[3333333];
long long ans;
int main() {
  long long a, b, p, first;
  a = read(), b = read(), p = read(), first = read();
  mo[0] = 1;
  for (long long i = 1; i <= p - 1; i++) {
    mo[i] = mo[i - 1] * a % p;
  }
  for (long long i = 1; i <= p - 1; i++) {
    if (first < i) continue;
    long long lim = (first - i) / (p - 1);
    long long ned = inv(mo[i], p) * b % p;
    ned = (i - ned + p) % p;
    if (lim < ned) continue;
    ans = ans + (lim - ned) / p + 1;
  }
  cout << ans << endl;
  return 0;
}

```