CF1152F1.Neko Rules the Catniverse (Small Version)

This problem is same as the next one, but has smaller 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^5$, $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^5$，$1 \le k \le \min(n, 12)$，$1 \le m \le 4$）——分别表示猫宇宙中的行星数量、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 恰好访问 $2$ 颗行星的方式共有 $9$ 种：

• $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 可以以任意顺序访问所有行星，因此 Neko 访问所有行星的方式共有 $5! = 120$ 种。

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