CF1152F2 Neko Rules the Catniverse (Large Version)

本题与前一题相同，但数据范围更大。 Aki 正在玩一款新的视频游戏。在游戏中，他将操控巨猫 Neko 在 Catniverse 的各个星球之间飞行。 Catniverse 中共有 $n$ 个星球，编号从 $1$ 到 $n$。游戏开始时，Aki 选择 Neko 的初始所在星球。然后，Aki 进行 $k-1$ 次移动，每次移动将 Neko 从当前星球 $x$ 移动到另一个星球 $y$，满足： - 星球 $y$ 尚未被访问过。 - $1 \leq y \leq x + m$（其中 $m$ 是输入中给定的一个固定常数）。 这样，Neko 将恰好访问 $k$ 个不同的星球。如果存在某个下标 $i$，使得第一种访问方式的第 $i$ 个访问星球与第二种方式的第 $i$ 个访问星球不同，则认为两种访问方式不同。 问 Neko 以这种方式访问恰好 $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$）——Catniverse 中的星球数量、Neko 需要访问的星球数量以及给定的常数 $m$。

输出一个整数，表示 Neko 访问恰好 $k$ 个星球的不同方案数。由于答案可能很大，请输出答案对 $10^9 + 7$ 取模后的结果。

在第一个样例中，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$ 个星球（即初始所在星球），共有 $100$ 种选择起始星球的方式。 由 ChatGPT 4.1 翻译