不看数据范围，本题和动物园特别像，
小L有一座环形花园，沿花园的顺时针方向，他把各个花圃编号为1~N(2<=N<=10^15)。他的环形花园每天都会换一个新花样，但他的花园都不外乎一个规则，任意相邻M(2<=M<=5,M<=N)个花圃中有不超过K(1<=K<M)个C形的花圃，其余花圃均为P形的花圃。
例如，N=10,M=5,K=3。则
CCPCPPPPCC 是一种不符合规则的花圃；
CCPPPPCPCP 是一种符合规则的花圃。
请帮小L求出符合规则的花园种数Mod 1000000007
由于请您编写一个程序解决此题。
40%的数据中，N<=20；
60%的数据中，M=2；
80%的数据中，N<=10^5。
100%的数据中，N<=10^15。
就是最后两个点不能过，
不过我们可以把 i -> j 状态存在矩阵中，做出一张floyd表，
然后logn矩阵加速
#include<cstdio> #include<cstdlib> #define ll long long using namespace std; ll n,mod=1000000007; int m,mm; int tot,st[35]; struct node { ll d[35][35]; }relate,ans,t; void mul(node &a ,node b ) { for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) for(int k=1;k<=tot;k++) t.d[i][j]=(t.d[i][j]+a.d[i][k]*b.d[k][j]%mod)%mod; for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) a.d[i][j]=t.d[i][j],t.d[i][j]=0; } ll sum; int main() { scanf("%lld%d%d",&n,&m,&mm); int mx=(1<<m)-1; for(int i=0;i<=mx;i++) { int x=i,cnt=0; while(x) if(x&1) cnt++,x>>=1; else x>>=1; if(cnt<=mm) st[++tot]=i; } int sd1=mx^(1<<m-1),sd2=mx^1; for(int i=1;i<=tot;i++) for(int j=1;j<=tot;j++) if( (st[i]&sd1) == ((st[j]&sd2)>>1) ) relate.d[i][j]=1; ll a=1; for(int i=1;i<=tot;i++) ans.d[i][i]=1; while(a<=n) { if(n&a ) mul(ans,relate); a<<=1,mul(relate,relate); } for(int i=1;i<=tot;i++) sum=(sum+ans.d[i][i])%mod; printf("%lld\n",sum); return 0; }