#include using namespace std; #define DEBUG(x) cout<<#x<<": "< #define vl vector #define vii vector< vector > #define vll vector< vector > #define vs vector #define pii pair #define pis pair #define psi pair #define pll pair #define fi first #define se second #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define in(x, a, b) a <= x && x < b const int inf = 1000000001; const ll INF = 2e18; const ll MOD = 1000000007; //const ll mod = 1000000009; const double pi = 3.14159265358979323846; #define Sp(p) cout< vec; typedef vector mat; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); bool flag = false; for (int i = 0; i < A.size(); i++) { for (int k = 0; k < B.size(); k++) { for (int j = 0; j < B[0].size(); j++) { C[i][j] = C[i][j] + A[i][k] * B[k][j]; if (i == 1) { if (C[i][j] >= MOD) { flag = true; } } C[i][j] %= MOD; } } } if (flag) { rep (k, C[1].size()) { C[1][k] = 0; } } flag = true; rep (i, 4) { if (A[1][i] + B[1][i] != 0) { flag = false; } } if (flag) { rep (k, C[1].size()) { C[1][k] = 0; } } return C; } vec mul(mat &A, vec &B) { vec C(A.size()); bool flag = false; for (int i = 0; i < A.size(); i++) { for (int j = 0; j < B.size(); j++) { C[i] += A[i][j] * B[j]; if (i == 1 && C[i] >= MOD) { C[i] = 0; } else { C[i] %= MOD; } } } return C; } mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); i++) { B[i][i] = 1; } while (n > 0) { if (n & 1)B = mul(A, B); A = mul(A, A); n >>= 1; } return B; } int main() { ll n,b,d; cin >> n >> b >> d; mat A = {{d + 1, 0, d, d}, {0, d + 1, 0, d}, {0, 0, 1, 1}, {0, 0, 0, 1}}; vec x1 = {d, d, 1, 1}; mat Ab = pow(A, b - 1); vec xb = mul(Ab, x1); ll allsize = xb[0]; int i = 0; vector numsize; while (true) { mat A2 = pow(A, i); vec x = mul(A2, x1); //DEBUG_VEC(x); if (x[1] == 0) { break; } numsize.push_back(pll(x[1], x[0])); i++; } //DEBUG(allsize); /* rep (i, numsize.size()) { cout << numsize[i].first << " " << numsize[i].second << endl; } //*/ ll now = 0; for (int i = numsize.size() - 1; i >= 0; i--) { if (n == numsize[i].first) { now += numsize[i].second; now %= MOD; break; } ll num = numsize[i].first + 1, sz = (numsize[i].second + (i + 2)) % MOD; ll kosuu = n / num; if (kosuu == d + 1) { kosuu--; } now += kosuu * sz % MOD; now %= MOD; n -= num * kosuu; //DEBUG(i); //DEBUG(now); //DEBUG(n); } now += n; now %= MOD; cout << (allsize - now + 3*MOD) % MOD << endl; }