F2. Неко захватывает кошковселенную (усложнённая версия)
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эта задача такая же как и предыдущая, но с большими ограничениями.

Аки играет в новую видео-игру. В этой игре он управляет Неко, огромным котом, способным перемещаться между планетами кошковселенной.

Кошковселенная состоит из $$$n$$$ планет, пронумерованных от $$$1$$$ до $$$n$$$. В начале игры Аки выбирает планету, на которой изначально находится Неко. Затем Аки совершает $$$k - 1$$$ ходов, где за один ход Аки перемещает Неко с текущей планеты $$$x$$$ на какую-то планету $$$y$$$, такую что:

  • Планета $$$y$$$ ещё не посещена.
  • $$$1 \leq y \leq x + m$$$ (где $$$m$$$ это фиксированная константа, заданная во входных данных)

Таким образом Неко посетит ровно $$$k$$$ различных планет. Два способа посещений планет называются различными, если существует индекс $$$i$$$, что $$$i$$$-я планета в первом способе отличается от $$$i$$$-й планеты во втором способе.

Сколько всего существует способов посетить $$$k$$$ планет таким образом? Так как ответ может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.

Входные данные

Единственная строка входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$m$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le k \le \min(n, 12)$$$, $$$1 \le m \le 4$$$) — количество планет в кошковселенной, количество планет, которое нужно посетить и вышеупомянутая константа $$$m$$$.

Выходные данные

Выведите ровно одно целое число — количество способов, которыми Неко может посетить $$$k$$$ планет. Так как это число может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.

Примеры
Входные данные
3 3 1
Выходные данные
4
Входные данные
4 2 1
Выходные данные
9
Входные данные
5 5 4
Выходные данные
120
Входные данные
100 1 2
Выходные данные
100
Примечание

В первом примере есть $$$4$$$ способа для Неко посетить все планеты:

  • $$$1 \rightarrow 2 \rightarrow 3$$$
  • $$$2 \rightarrow 3 \rightarrow 1$$$
  • $$$3 \rightarrow 1 \rightarrow 2$$$
  • $$$3 \rightarrow 2 \rightarrow 1$$$

Во втором примере есть $$$9$$$ способов посетить ровно $$$2$$$ планеты:

  • $$$1 \rightarrow 2$$$
  • $$$2 \rightarrow 1$$$
  • $$$2 \rightarrow 3$$$
  • $$$3 \rightarrow 1$$$
  • $$$3 \rightarrow 2$$$
  • $$$3 \rightarrow 4$$$
  • $$$4 \rightarrow 1$$$
  • $$$4 \rightarrow 2$$$
  • $$$4 \rightarrow 3$$$

В третьем примере $$$m = 4$$$ и Неко может посетить все планеты в любом порядке, так что всего есть $$$5! = 120$$$ способов всё посетить.

В четвёртом примере Неко должен посетить только $$$1$$$ планету (которая в частности будет начальной планетой маршрута), а значит есть $$$100$$$ способов посетить одну планету.