#include <bits/stdc++.h>
using std::bitset;
using std::cerr;
using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::fill;
using std::ios_base;
using std::iterator;
using std::map;
using std::max;
using std::max_element;
using std::min;
using std::min_element;
using std::multimap;
using std::multiset;
using std::pair;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::stable_sort;
using std::stack;
using std::string;
using std::swap;
using std::unique;
using std::vector;
namespace MySpace {};
const long long inf = 1e18;
const long long infsmart = 1e12;
void Set(long long l, long long r, long long L, long long R, long long V,
         long long val) {
  if (l <= L && R <= r) {
    return;
  }
  if (r <= L || R <= l) return;
}
long long Get(long long l, long long r, long long L, long long R, long long V) {
  if (l <= L && R <= r) {
  }
  if (r <= L || R <= l) {
    return 0;
  }
}
const long long MOD = 1e9 + 7;
long long a, b, p, x, ans;
long long inq(long long x, long long y) {
  if (y == 0) return 1;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % p * x % p;
  return l * l % p;
}
long long compared(long long r1, long long m1, long long r2, long long m2) {
  long long y = 1;
  long long x = 1;
  y *= r1 - r2;
  x *= r1 - r2;
  long long a = x * m1 + r1;
  a = (a + 4 * m1 * m2) % (m1 * m2);
  return a;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> a >> b >> p >> x;
  long long A = 1;
  for (long long d = 0; d < p - 1; d++) {
    long long r = inq(A, p - 2) * b % p;
    r = compared(d, p - 1, r, p);
    long long m = p * (p - 1);
    long long blocks = x / m;
    ans += blocks;
    if (x % m >= r) ans++;
    A = A * a % p;
  }
  cout << ans;
}

### Prompt

Your task is to create a Cpp solution to 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 std::bitset;
using std::cerr;
using std::cin;
using std::cout;
using std::deque;
using std::endl;
using std::fill;
using std::ios_base;
using std::iterator;
using std::map;
using std::max;
using std::max_element;
using std::min;
using std::min_element;
using std::multimap;
using std::multiset;
using std::pair;
using std::queue;
using std::reverse;
using std::set;
using std::sort;
using std::stable_sort;
using std::stack;
using std::string;
using std::swap;
using std::unique;
using std::vector;
namespace MySpace {};
const long long inf = 1e18;
const long long infsmart = 1e12;
void Set(long long l, long long r, long long L, long long R, long long V,
         long long val) {
  if (l <= L && R <= r) {
    return;
  }
  if (r <= L || R <= l) return;
}
long long Get(long long l, long long r, long long L, long long R, long long V) {
  if (l <= L && R <= r) {
  }
  if (r <= L || R <= l) {
    return 0;
  }
}
const long long MOD = 1e9 + 7;
long long a, b, p, x, ans;
long long inq(long long x, long long y) {
  if (y == 0) return 1;
  long long l = inq(x, y / 2);
  if (y % 2) return l * l % p * x % p;
  return l * l % p;
}
long long compared(long long r1, long long m1, long long r2, long long m2) {
  long long y = 1;
  long long x = 1;
  y *= r1 - r2;
  x *= r1 - r2;
  long long a = x * m1 + r1;
  a = (a + 4 * m1 * m2) % (m1 * m2);
  return a;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> a >> b >> p >> x;
  long long A = 1;
  for (long long d = 0; d < p - 1; d++) {
    long long r = inq(A, p - 2) * b % p;
    r = compared(d, p - 1, r, p);
    long long m = p * (p - 1);
    long long blocks = x / m;
    ans += blocks;
    if (x % m >= r) ans++;
    A = A * a % p;
  }
  cout << ans;
}

```