88pts 求调/求 Hack

#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[30000001];
long long c[4],d[4],t[4];
void f(long long*a,long long*b,long long p)
{   
    t[0]=((a[0]*b[0])%p+(a[1]*b[2])%p)%p;
    t[1]=((a[0]*b[1])%p+(a[1]*b[3])%p)%p;
    t[2]=((a[2]*b[0])%p+(a[3]*b[2])%p)%p;
    t[3]=((a[2]*b[1])%p+(a[3]*b[3])%p)%p;
    a[0]=t[0],a[1]=t[1],a[2]=t[2],a[3]=t[3];
}
 void g(long long n,long long p)
{
    c[1]=c[2]=d[0]=0,c[0]=c[3]=d[1]=d[2]=d[3]=1;
    while(n)
    {
    	if(n&1)f(c,d,p);
    	f(d,d,p);
    	n>>=1;
	}
}
signed main()
{
	long long p,q,r=1;
	__int128 n=0;
	cin>>s>>p;
	q=p;
	for(long long i=2;i*i<=p;i++)
	{
		if(q%i==0)
		{
			while(q%i==0)q/=i;
			r*=i*i-1;
		}	
    }
    if(q!=1)r*=q*q-1;
	for(int i=0;s[i];i++)n=(n*10+s[i]-'0')%r;
	g((long long)n,p);
	cout<<c[1]<<endl;
	return 0;
}