C++ Code
#include <iostream>
using namespace std;
const long long MOD=1000000007;
int k;
void multiply(long long mat1[41][41],long long mat2[41][41],long long res[41][41]){
long long temp[41][41]={0};
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
for(int l=0;l<k;l++){
temp[i][j]+=(mat1[i][l]*mat2[l][j])%MOD;
temp[i][j]%=MOD;
}
}
}
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
res[i][j]=temp[i][j];
}
}
}
void power(long long matrix[41][41],long long d,long long result[41][41]){
long long base[41][41];
for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
base[i][j]=matrix[i][j];
}
}
while(d>0){
if(d & 1)multiply(result,base,result);
multiply(base,base,base);
d >>=1;
}
void matvec(long long M[41][41], long long day[41], long long out[41]) {
for (int i=0;i<k;i++) out[i] = 0;
for (int i=0;i<k;i++) {
for (int j = 0; j < k; j++) {
out[i] = (out[i] + M[i][j] * day[j]) % MOD;
}
}
}
int main(){
int n;
long long d;
cin>>n>>k>>d;
long long matrix[41][41]={0};
long long powmatrix[41][41]={0};
for(int i=0;i<k;i++){
matrix[0][i]=i+1;
}
for(int i=1;i<k;i++){
matrix[i][i-1]=1;
}
for(int i=0;i<k;i++){
powmatrix[i][i]=1;
}
power(matrix,d,powmatrix);
long long day0[41]={0};
day0[0]=n;
long long dayd[41];
matvec(powmatrix,day0,dayd);
long long sum=0;
for(int i=0;i<k;i++){
sum+=dayd[i];
sum%=MOD;
}
cout<<sum;
return 0;
}