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;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=1e6+5;
int main() {
    ll n,x,m;cin>>n>>x>>m;
    if(n==1) return cout<<x<<'\n',0;
    map<int,ll> pos,ps;
    pos[x]=1;ps[1]=x;
    ll now=x,sum=x;
    for(int i=2;i<=m+2;i++) {
    	now=now*now%m;sum+=now;
    	if(i==n) return cout<<sum<<endl,0;
    	if(pos[now]) {
    		ll need=n-pos[now]+1;
    		ll circle=i-pos[now];
    		return cout<<ps[pos[now]-1]+need/circle*(sum-ps[pos[now]])+ps[pos[now]+need%circle-1]-ps[pos[now]-1],0;
    	}else {
    		pos[now]=i;
    		ps[i]=sum;
    	}
    }
    return 0;
}