Let us denote by f(x, m) the remainder of the Euclidean division of x by m.

Let A be the sequence that is defined by the initial value A_1=X and the recurrence relation A_{n+1} = f(A_n^2, M). Find \displaystyle{\sum_{i=1}^N A_i}.

Constraints

* 1 \leq N \leq 10^{10}
* 0 \leq X < M \leq 10^5
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N X M


Output

Print \displaystyle{\sum_{i=1}^N A_i}.

Examples

Input

6 2 1001


Output

1369


Input

1000 2 16


Output

6


Input

10000000000 10 99959


Output

492443256176507
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
  ll n, x, m;
  cin >> n >> x >> m;

  vector<ll> v{0, x};
  ll h;
  {
    set<ll> s{x};
    ll e = x;
    while (s.count(e = e * e % m) == 0) {
      v.push_back(e);
      s.insert(e);
    }
    h = find(v.begin(), v.end(), e) - v.begin() - 1;
  }
  ll l = v.size() - 1;
  bool z = v.back() == 0;
  for (int i = 0; i + 1 < v.size(); i++) v[i + 1] += v[i];

  ll r = 0;
  if (n < h || z) {
    r += v[min(l, n)];
  } else {
    r += (n - h) / (l - h) * (v[l] - v[h]);
    r += v[h + (n - h) % (l - h)];
  }
  cout << r << endl;
}
