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
// Author: HarshKumar

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll N = 1e6 + 6, M = 1e9 + 7;
ll f[N], s[N];
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    ll n, i, x, m, p;
    cin >> n >> x >> m;
    s[1] = p = x;
    f[x] = 1;
    for (i = 2; i <= n; i++)
    {
        x = p * p % m;
        p = x;
        s[i] = s[i - 1] + x;
        if (f[x])
            break;
        f[x] = i;
    }
    if (i == n + 1)
        return cout << s[n], 0;
    ll q = (n - f[x] + 1) / (i - f[x]);
    ll r = (n - f[x] + 1) % (i - f[x]);
    ll ans = (s[i] - s[f[x]]) * q + s[f[x] + r - 1];
    cout << ans;
}