TLE #22 和 #25。
开大随机数范围可以修复掉 TLE，但会爆出大量 WA（包括这两个点）。

#include<bits/stdc++.h>
using namespace std;
long long d[2][262145][4],t[4],k[4];
char s[30000001];
unordered_map<long long,int>m;
mt19937_64 rnd(time(0));
union v
{
	long long a;
	int b[2];
}c;
inline void f(long long*a,long long*b,int 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(int o,int n,int p)
{
	if(!(d[o][n][3]||d[o][n][2])&&n!=0)
	{
		g(o,n>>1,p);
		d[o][n][0]=d[o][n>>1][0];
		d[o][n][1]=d[o][n>>1][1];
		d[o][n][2]=d[o][n>>1][2];
		d[o][n][3]=d[o][n>>1][3]; 
		f(d[o][n],d[o][n],p);
		if(n&1)f(d[o][n],d[o][1],p);
	}
}
inline long long*h(long long n,int p)
{
	int a=n&262143,b=n>>18;
	g(0,a,p);
	g(1,b,p);
	k[0]=d[0][a][0];
	k[1]=d[0][a][1];
	k[2]=d[0][a][2];
	k[3]=d[0][a][3]; 
	if(b)f(k,d[1][b],p);
	return k;
}
int main()
{
	int p;
	long long l,n=0;
    cin>>s>>p;
    if(s[1])
	d[0][1][0]=0,d[0][1][1]=d[0][1][2]=d[0][1][3]=1;
	g(0,262144,p);
	d[1][1][0]=d[0][262144][0],d[1][1][1]=d[0][262144][1],d[1][1][2]=d[0][262144][2],d[1][1][3]=d[0][262144][3];
    while(1)
    {
    	int a=rnd()%(2147483645)+1;
    	c.b[0]=h(a,p)[1],c.b[1]=h(a+1,p)[1];
    	if((l=m[c.a])&&l!=a)
    	{
    		l-=a;
    		break;
		}
		m[c.a]=a;
	}
	for(int i=0;s[i];i++)n=(n*10+s[i]-'0')%l;
	cout<<h(n,p)[1]<<endl;
    return 0;
}