快速幂
ll powermod(ll a,ll n) { ll ans=1; a%=MOD; while(n) { if(n&1) ans=ans*a%MOD; a=a*a%MOD; n>>=1; } return ans; }快速矩阵幂
const ll MOD=1e9+7; const int Matsize=2; struct Mat { ll mat[Matsize][Matsize]; void init() { for(int i=0;i<Matsize;i++) { for(int j=0;j<Matsize;j++) mat[i][j]=0; mat[i][i]=1; } } Mat operator*(const Mat &t)const { Mat ans; memset(ans.mat,0,sizeof(ans.mat)); for(int k=0;k<Matsize;k++) for(int i=0;i<Matsize;i++) for(int j=0;j<Matsize;j++) ans.mat[i][j]=(ans.mat[i][j]+mat[i][k]*t.mat[k][j])%MOD; return ans; } }; Mat Q { 1,1, 1,0 }; Mat A; Mat Pow(ll m) { Mat res,mt=Q; res.init(); while(m) { if(m&1) res=res*mt; mt=mt*mt; m>>=1; } return res; } 二分求等比数列之和 ll powersummod(int q,ll n) //1+q+q^2+q^3+...+q^n { if(n==0) return 1; if(n==1) return (1+q)%MOD; if(n&1) return (1+powermod(q,n/2+1))*powersummod(q,n/2)%MOD; else return (powermod(q,n)+(1+powermod(q,(n-1)/2+1))*powersummod(q,(n-1)/2)%MOD)%MOD; } ll powersummod(int q,ll n) //q+q^2+q^3+...+q^n { if(n==1) return q%MOD; if(n&1) return (powermod(q,n)+(1+powermod(q,(n-1)/2))*powersummod(q,(n-1)/2)%MOD)%MOD; else return (1+powermod(q,n/2))*powersummod(q,n/2)%MOD; }