rt 84pts

2WA 2RE

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,tem,pi=1,n,cnt;
ll base[3][3],ans[3][3];
char ch[30000010];
inline ll G(ll p) {
    if(p%5==1 || p%5==4) return p-1;
    else return 2*(p+1);
}
inline void cal() {
    for(register ll i=2;i*i<=p;i++) {
        if(!(tem%i)) pi*=G(i),tem/=i;
        while(!(tem%i)) pi*=i,tem/=i;
    }
    pi*=G(tem);
}
inline void read() {
    ch[++cnt]=getchar();
    while(ch[cnt]>='0'&&ch[cnt]<='9') {ch[++cnt]=getchar();}
    cnt--;
}
inline void op1() {
    ll c[3][3]={0};
    for(register int i=1;i<=2;i++)
        for(register int j=1;j<=2;j++)
            for(register int k=1;k<=2;k++)
                c[i][j]=(c[i][j]+ans[i][k]*base[k][j])%p;
    for(register int i=1;i<=2;i++)
        for(register int j=1;j<=2;j++)
            ans[i][j]=c[i][j];
}
inline void op2() {
    ll c[3][3]={0};
    for(register int i=1;i<=2;i++)
        for(register int j=1;j<=2;j++)
            for(register int k=1;k<=2;k++)
                c[i][j]=(c[i][j]+base[i][k]*base[k][j])%p;
    for(register int i=1;i<=2;i++)
        for(register int j=1;j<=2;j++)
            base[i][j]=c[i][j];
}
int main() {
    read();
    scanf("%lld",&p);tem=p;
    if(p==1) {printf("0");return 0;}
    cal();
    for(register ll i=1;i<=cnt;i++) n=(n*10+ch[i]-'0')%pi;n-=2;
    if(n==-2) {printf("0");return 0;} if(n<=0) {printf("1");return 0;}
    for(register int i=1;i<=2;i++) ans[i][i]=1;
    base[1][1]=base[1][2]=base[2][1]=1;
    while(n) {
        if(n&1) op1();
        op2();n>>=1;
    }
    printf("%lld",(ans[1][1]+ans[1][2])%p);
    return 0;
}