#include <bits/stdc++.h>
using namespace std;
tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
  if (a == 0) return make_tuple(b, 0, 1);
  tuple<long long, long long, long long> t = ext_gcd(b % a, a);
  return make_tuple(get<0>(t), get<2>(t) - (b / a) * (get<1>(t)), get<1>(t));
}
long long poww(long long x, long long n, long long mod) {
  if (x == 0) return 0;
  if (n == 0) return 1;
  if (n == 1) return x % mod;
  long long ans = poww(x, n / 2, mod) % mod;
  if (n % 2)
    ans = (ans * ans % mod) * x;
  else
    ans = ans * ans % mod;
  ans %= mod;
  return ans % mod;
}
map<long long, bool> vis;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long tc = 1;
  long long Case = 1;
  while (tc--) {
    long long x, a, b, p;
    cin >> a >> b >> p >> x;
    long long ans = 0;
    long long po = poww(a, p - 2, p);
    long long ai_inv = 1;
    long long P = p * (p - 1);
    for (int i = 0; i < p; i++) {
      long long mod1 = (b * ai_inv) % P;
      ai_inv *= po;
      ai_inv %= p;
      long long mod2 = i;
      long long n =
          (((((mod1) * (p - 1)) % P) * (p - 1)) % P + (i * p) % P) % P;
      if (vis[n]) continue;
      vis[n] = 1;
      ans += (x - n + P) / P;
    }
    cout << ans << endl;
  }
  return 0;
}

### Prompt

Create a solution in CPP for 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 namespace std;
tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
  if (a == 0) return make_tuple(b, 0, 1);
  tuple<long long, long long, long long> t = ext_gcd(b % a, a);
  return make_tuple(get<0>(t), get<2>(t) - (b / a) * (get<1>(t)), get<1>(t));
}
long long poww(long long x, long long n, long long mod) {
  if (x == 0) return 0;
  if (n == 0) return 1;
  if (n == 1) return x % mod;
  long long ans = poww(x, n / 2, mod) % mod;
  if (n % 2)
    ans = (ans * ans % mod) * x;
  else
    ans = ans * ans % mod;
  ans %= mod;
  return ans % mod;
}
map<long long, bool> vis;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  long long tc = 1;
  long long Case = 1;
  while (tc--) {
    long long x, a, b, p;
    cin >> a >> b >> p >> x;
    long long ans = 0;
    long long po = poww(a, p - 2, p);
    long long ai_inv = 1;
    long long P = p * (p - 1);
    for (int i = 0; i < p; i++) {
      long long mod1 = (b * ai_inv) % P;
      ai_inv *= po;
      ai_inv %= p;
      long long mod2 = i;
      long long n =
          (((((mod1) * (p - 1)) % P) * (p - 1)) % P + (i * p) % P) % P;
      if (vis[n]) continue;
      vis[n] = 1;
      ans += (x - n + P) / P;
    }
    cout << ans << endl;
  }
  return 0;
}

```