CF1152F2.Neko Rules the Catniverse (Large Version)

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 \leq y \leq 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$.

本题与上一题相同，但约束条件更大。

Aki 正在玩一款新视频游戏。在该游戏中，他将操控一只名为 Neko 的巨型猫，在“猫宇宙”（Catniverse）中的各个行星之间飞行。

猫宇宙中共有 $n$ 颗行星，编号为 $1$ 到 $n$。游戏开始时，Aki 选择一颗行星作为 Neko 的初始位置。随后 Aki 执行 $k - 1$ 次移动；每次移动中，Neko 从当前所在的行星 $x$ 飞往另一颗尚未访问过的行星 $y$，且需满足：

• 行星 $y$ 尚未被访问过；
• $1 \leq y \leq x + m$（其中 $m$ 是输入中给定的一个固定常数）。

如此，Neko 将恰好访问 $k$ 颗互不相同的行星。若两种访问行星的方式在某个下标 $i$ 处所访问的第 $i$ 颗行星不同，则称这两种方式不同。

问：按照上述规则访问 $k$ 颗行星的总方案数是多少？由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

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

唯一一行包含三个整数 $n$、$k$ 和 $m$（$1 \le n \le 10^9$，$1 \le k \le \min(n, 12)$，$1 \le m \le 4$）——分别表示 Catniverse 中的行星数量、Neko 需要访问的行星数量，以及给定的常数 $m$。

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$.

输出一个整数——Neko 恰好访问 $k$ 个行星的不同方式数目。由于答案可能非常大，请对 $10^9 + 7$ 取模后输出。

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

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

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

• $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$

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.

在第一个例子中，Neko 有 $4$ 种方式访问所有行星：

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

在第二个例子中，Neko 有 $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$ 时，Neko 可以以任意顺序访问所有行星，因此共有 $5! = 120$ 种方式访问所有行星。

在第四个例子中，Neko 仅恰好访问 $1$ 颗行星（即他初始所在的行星），且 Neko 有 $100$ 种方式选择起始行星。