CF1152F1 Neko Rules the Catniverse (Small 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$ 个访问星球不同，则这两种访问方式被认为是不同的。 问以这种方式访问恰好 $k$ 个星球的不同方案总数是多少？由于答案可能很大，请输出答案对 $10^9 + 7$ 取模后的结果。

一行，包含三个整数 $n$、$k$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq k \leq \min(n, 12)$，$1 \leq m \leq 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 翻译