斐波那契数列模$10^m$的循环节为$6\times10^m$，于是从低位到高位dfs即可。

#include
     
      #include
      
       #define N 20typedef long long ll;typedef unsigned long long ull;int n,i,flag;char a[N];ll mo[N],b[N];ull ans;inline ull mul(ull a,ull b,ull P){ull t=0;for(;b;b>>=1,a=(a+a)%P)if(b&1)t=(t+a)%P;return t;}void cal(ll n,ll&x,ll&y,ll P){  if(!n){x=0,y=1;return;}  if(n==1){x=y=1;return;}  if(n&1){    cal(n-1,y,x,P);    y=(1ULL*y+x)%P;    return;  }  ll a,b;  cal(n>>1,a,b,P);  x=(mul(a,b,P)+mul(a,b