#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

int num[1000001],id[1000001];
int main()
{
    int n,A,B;
    int i,j;
    while(~scanf("%d%d%d",&n,&A,&B))
    {
        int front=0;
        int top=0;
        __int64 x=1,sum=1;
        for(i=1;i<=n;i++)
        {
            x=(x*A)%B;
            while(front<top&&num[top]>x)
            top--;
            num[++top]=x;
            id[top]=i;
            while(id[front+1]<i-A) front++;
            sum=(sum*num[front+1])%B;
        }
        printf("%I64d\n",sum);
    }    
    return 0;
}

hdu 3706 单调队列水题