C++ Program
#include <iostream>
using namespace std;
const long long mod = 1000000007;
const int maxk = 45;
int n, k; long long d;
void mul(long long A[maxk][maxk], long long B[maxk][maxk], long long C[maxk][maxk], int size) {
long long temp[maxk][maxk] = {0};
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
long long sum = 0;
for(int t=0;t<size;t++){
sum = (sum + A[i][t]*B[t][j]) % mod;
}
temp[i][j] = sum;
}
}
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
C[i][j] = temp[i][j];
}
}
}
void power(long long M[maxk][maxk], long long exp, int size, long long R[maxk][maxk]) {
long long temp[maxk][maxk];
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
R[i][j] = (i==j);
}
}
while(exp > 0){
if(exp & 1){
mul(R, M, temp, size);
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
R[i][j] = temp[i][j];
}
mul(M, M, temp, size);
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
M[i][j] = temp[i][j];
exp >>= 1;
}
}
int main() {
cin >> n >> k >> d;
if(d == 0){
cout << n % mod << endl;
return 0;
}
long long M[maxk][maxk] = {0};
for(int i=0;i<k-1;i++){
M[i+1][i] = 1;
}
for(int j=0;j<k;j++){
M[0][j] = j+1;
}
long long R[maxk][maxk];
power(M, d, k, R);
long long it[maxk] = {0};
it[0] = n;
long long result[maxk] = {0};
for(int i=0;i<k;i++){
long long sum=0;
for(int j=0;j<k;j++){
sum = (sum + R[i][j] * it[j]) % mod;
}
result[i] = sum;
}
long long total = 0;
for(int i=0;i<k;i++){
total = (total + result[i]) % mod;
}
cout << total << endl;
return 0;
}