易得递推式为f[i]=f[i-1]+f[i-M] 最终答案即为f[N]. 由于N很大，用矩阵快速幂求解。

code:

#include
    
     using namespace std;typedef long long ll;const int MOD=1e9+7;ll n,m;struct mat{    ll a[105][105];};mat mat_mul(mat x,mat y){    mat res;    memset(res.a,0,sizeof(res.a));    for(int i=0;i
     
      >1;    }    c=res;    ll ans=c.a[m-1][0]*2%MOD;    for(int j=1;j
      
       >n>>m;        mat_pow(n);    return 0;}