This problem is same as the previous one, but has larger constraints.

Aki is playing a new video game. In the video game, he will control Neko, the giant cat, to fly between planets in the Catniverse.

There are n planets in the Catniverse, numbered from 1 to n. At the beginning of the game, Aki chooses the planet where Neko is initially located. Then Aki performs k - 1 moves, where in each move Neko is moved from the current planet x to some other planet y such that:

  * Planet y is not visited yet. 
  * 1 ≤ y ≤ x + m (where m is a fixed constant given in the input) 



This way, Neko will visit exactly k different planets. Two ways of visiting planets are called different if there is some index i such that, the i-th planet visited in the first way is different from the i-th planet visited in the second way.

What is the total number of ways to visit k planets this way? Since the answer can be quite large, print it modulo 10^9 + 7.

Input

The only line contains three integers n, k and m (1 ≤ n ≤ 10^9, 1 ≤ k ≤ min(n, 12), 1 ≤ m ≤ 4) — the number of planets in the Catniverse, the number of planets Neko needs to visit and the said constant m.

Output

Print exactly one integer — the number of different ways Neko can visit exactly k planets. Since the answer can be quite large, print it modulo 10^9 + 7.

Examples

Input


3 3 1


Output


4


Input


4 2 1


Output


9


Input


5 5 4


Output


120


Input


100 1 2


Output


100

Note

In the first example, there are 4 ways Neko can visit all the planets:

  * 1 → 2 → 3 
  * 2 → 3 → 1 
  * 3 → 1 → 2 
  * 3 → 2 → 1 



In the second example, there are 9 ways Neko can visit exactly 2 planets:

  * 1 → 2 
  * 2 → 1 
  * 2 → 3 
  * 3 → 1 
  * 3 → 2 
  * 3 → 4 
  * 4 → 1 
  * 4 → 2 
  * 4 → 3 



In the third example, with m = 4, Neko can visit all the planets in any order, so there are 5! = 120 ways Neko can visit all the planets.

In the fourth example, Neko only visit exactly 1 planet (which is also the planet he initially located), and there are 100 ways to choose the starting planet for Neko.
#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
  in >> p.first >> p.second;
  return in;
}
template <typename T>
istream &operator>>(istream &in, vector<T> &v) {
  for (auto &x : v) in >> x;
  return in;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {
  out << "[" << p.first << ", " << p.second << "]"
      << "\n";
  return out;
}
inline int gc() {
  static const int BUF = 1e7;
  static char buf[BUF], *bg = buf + BUF, *ed = bg;
  if (bg == ed) fread(bg = buf, 1, BUF, stdin);
  return *bg++;
}
inline int ri() {
  int x = 0, f = 1, c = gc();
  for (; c < 48 || c > 57; f = c == '-' ? -1 : f, c = gc())
    ;
  for (; c > 47 && c < 58; x = x * 10 + c - 48, c = gc())
    ;
  return x * f;
}
const double EPS = 1e-10;
const long long inf = 0x7fffffff;
const long long infLL = 0x7fffffffffffffffLL;
const long long mod = 1e9 + 7;
const int maxN = 1e5 + 7;
const long long ONE = 1;
const long long evenBits = 0xaaaaaaaaaaaaaaaa;
const long long oddBits = 0x5555555555555555;
void add_mod(long long &a, long long b) { a = (a + b) % mod; }
struct Matrix {
  int row, col;
  long long MOD;
  vector<vector<long long> > mat;
  Matrix(int r, int c, long long p = mod) : row(r), col(c), MOD(p) {
    mat.assign(r, vector<long long>(c, 0));
  }
  Matrix(const Matrix &x, long long p = mod) : MOD(p) {
    mat = x.mat;
    row = x.row;
    col = x.col;
  }
  Matrix(const vector<vector<long long> > &A, long long p = mod) : MOD(p) {
    mat = A;
    row = A.size();
    col = A[0].size();
  }
  inline void E(int x = 1) {
    assert(row == col);
    for (int i = 0; i < (row); ++i) mat[i][i] = x;
  }
  inline vector<long long> &operator[](int x) {
    assert(x >= 0 && x < row);
    return mat[x];
  }
  inline Matrix operator=(const vector<vector<long long> > &x) {
    row = x.size();
    col = x[0].size();
    mat = x;
    return *this;
  }
  inline Matrix operator+(const Matrix &x) {
    assert(row == x.row && col == x.col);
    Matrix ret(row, col);
    for (int i = 0; i < (row); ++i) {
      for (int j = 0; j < (col); ++j) {
        ret.mat[i][j] = mat[i][j] + x.mat[i][j];
        ret.mat[i][j] %= MOD;
      }
    }
    return ret;
  }
  inline Matrix operator*(const Matrix &x) {
    assert(col == x.row);
    Matrix ret(row, x.col);
    for (int k = 0; k < (x.col); ++k) {
      for (int i = 0; i < (row); ++i) {
        if (mat[i][k] == 0) continue;
        for (int j = 0; j < (x.col); ++j) {
          ret.mat[i][j] += mat[i][k] * x.mat[k][j];
          ret.mat[i][j] %= MOD;
        }
      }
    }
    return ret;
  }
  inline Matrix operator*=(const Matrix &x) { return *this = *this * x; }
  inline Matrix operator+=(const Matrix &x) { return *this = *this + x; }
  inline void print() {
    for (int i = 0; i < (row); ++i) {
      for (int j = 0; j < (col); ++j) {
        cout << mat[i][j] << " ";
      }
      cout << endl;
    }
  }
};
inline Matrix mat_pow_mod(Matrix x, long long y) {
  Matrix ret(x.row, x.col);
  ret.E();
  while (y) {
    if (y & 1) ret *= x;
    x *= x;
    y >>= 1;
  }
  return ret;
}
int n, k, m, maxSta;
long long ans;
int toId(int j, int sta) { return j * maxSta + sta; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> k >> m;
  maxSta = 1 << m;
  Matrix dp((k + 1) * maxSta, 1);
  dp.mat[0][0] = 1;
  Matrix base((k + 1) * maxSta, (k + 1) * maxSta);
  for (int j = 0; j < (k + 1); ++j) {
    for (int sta = 0; sta < (maxSta); ++sta) {
      int newsta = (sta << 1) % maxSta;
      int cur = toId(j, sta), newcur = toId(j, newsta);
      base.mat[newcur][cur] = 1;
      if (j < k) {
        newcur = toId(j + 1, newsta | 1);
        base.mat[newcur][cur] = __builtin_popcount(sta) + 1;
      }
    }
  }
  base = mat_pow_mod(base, n);
  dp = base * dp;
  for (int sta = 0; sta < (maxSta); ++sta)
    add_mod(ans, dp.mat[toId(k, sta)][0]);
  cout << ans << endl;
  return 0;
}
