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;
#pragma optimize("-O3")
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(const bool& b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(const A& v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T>
inline void _read(T& x) {
  cin >> x;
}
template <typename A, typename B>
inline void _read(pair<A, B>& x) {
  _read(x.first);
  _read(x.second);
}
template <typename T>
inline void _read(vector<T>& x) {
  for (auto& v : x) _read(v);
}
void R() {}
template <typename T, typename... U>
void R(T& head, U&... tail) {
  _read(head);
  R(tail...);
}
template <typename T>
inline void _write(const T& x) {
  cout << x << ' ';
}
template <typename A, typename B>
inline void _write(const pair<A, B>& x) {
  _write(x.first);
  _write(x.second);
}
template <typename T>
inline void _write(const vector<T>& in) {
  for (const auto& x : in) _write(x);
}
void W() { cout << '\n'; }
template <typename T, typename... U>
void W(const T& head, const U&... tail) {
  _write(head);
  W(tail...);
}
void go();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  go();
  return 0;
}
const int mod = 1e9 + 7;
const int maxn = 1 << 14;
long long Pow(long long a, long long n) {
  long long t = 1;
  for (; n; n >>= 1, (a *= a) %= mod)
    if (n & 1) (t *= a) %= mod;
  return t;
}
long long res[maxn], base[maxn], _c[maxn], _md[maxn];
vector<int> Md;
void mul(long long* a, long long* b, int k) {
  for (int i = 0; i < k + k; i++) _c[i] = 0;
  for (int i = 0; i < k; i++)
    if (a[i])
      for (int j = 0; j < k; j++) _c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
  for (int i = k + k - 1; i >= k; i--)
    if (_c[i])
      for (int j = 0; j < Md.size(); j++)
        _c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
  for (int i = 0; i < k; i++) a[i] = _c[i];
}
int solve(long long n, vector<int> a, vector<int> b) {
  long long ans = 0, pnt = 0;
  int k = a.size();
  assert(a.size() == b.size());
  for (int i = 0; i < k; i++) _md[k - 1 - i] = -a[i];
  _md[k] = 1;
  Md.clear();
  for (int i = 0; i < k; i++)
    if (_md[i] != 0) Md.push_back(i);
  for (int i = 0; i < k; i++) res[i] = base[i] = 0;
  res[0] = 1;
  while ((1LL << pnt) <= n) pnt++;
  for (int p = pnt; p >= 0; p--) {
    mul(res, res, k);
    if ((n >> p) & 1) {
      for (int i = k - 1; i >= 0; i--) res[i + 1] = res[i];
      res[0] = 0;
      for (int j = 0; j < Md.size(); j++)
        res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
    }
  }
  for (int i = 0; i < k; i++) ans = (ans + res[i] * b[i]) % mod;
  if (ans < 0) ans += mod;
  return ans;
}
vector<int> BM(vector<int> s) {
  vector<int> C(1, 1), B(1, 1);
  int L = 0, m = 1, b = 1;
  for (int n = 0; n < s.size(); n++) {
    long long d = 0;
    for (int i = 0; i <= L; i++) d = (d + (long long)C[i] * s[n - i]) % mod;
    if (d == 0)
      ++m;
    else if (2 * L <= n) {
      vector<int> T = C;
      long long c = mod - d * Pow(b, mod - 2) % mod;
      while (C.size() < B.size() + m) C.push_back(0);
      for (int i = 0; i < B.size(); i++) C[i + m] = (C[i + m] + c * B[i]) % mod;
      L = n + 1 - L, B = T, b = d, m = 1;
    } else {
      long long c = mod - d * Pow(b, mod - 2) % mod;
      while (C.size() < B.size() + m) C.push_back(0);
      for (int i = 0; i < B.size(); i++) C[i + m] = (C[i + m] + c * B[i]) % mod;
      ++m;
    }
  }
  return C;
}
int gao(vector<int> a, long long n) {
  vector<int> c = BM(a);
  c.erase(c.begin());
  for (int i = 0; i < c.size(); i++) c[i] = (mod - c[i]) % mod;
  return solve(n, c, vector<int>(a.begin(), a.begin() + c.size()));
}
const int M = 1 << 4;
const int N = 1 << 10;
const int K = 4;
int dp[N][M][1 << K];
void go() {
  int n, k, m;
  R(n, k, m);
  dp[0][0][0] = 1;
  for (int i = 0; i < 1000; i++)
    for (int j = 0; j <= k; j++)
      for (int s = 0; s < (1 << m); s++) {
        int t = (s << 1) % (1 << m);
        (dp[i + 1][j][t] += dp[i][j][s]) %= mod;
        if (j < k) {
          int w = __builtin_popcount(s) + 1;
          (dp[i + 1][j + 1][t | 1] += 1LL * w * dp[i][j][s] % mod) %= mod;
        }
      }
  vector<int> ans(1000);
  for (int i = 0; i < 1000; i++)
    for (int s = 0; s < (1 << m); s++) (ans[i] += dp[i][k][s]) %= mod;
  W(gao(ans, n));
}
