← 返回题目列表

Codeforces · 1152/F1

F1. Neko 统治猫世界(小版)

中文机器翻译题面 查看原题

这个问题与下一个问题相同,但约束较小。

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$$$个行星与第二种方式访问​​的第$$$i$$$个行星不同,则两种访问行星的方式被称为不同。

通过这种方式访问​​ $$$k$$$ 行星的方式总数是多少?由于答案可能相当大,因此打印它对 $$$10^9 + 7$$$ 取模。

输入

唯一一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le \min(n, 12)$$$, $$$1 \le m \le 4$$$) — Catniverse 中的行星数量,Neko 行星数量需要访问并表示常数$$$m$$$。

输出

精确打印一个整数——Neko 访问 $$$k$$$ 行星的不同方式的数量。由于答案可能相当大,因此打印它对 $$$10^9 + 7$$$ 取模。

示例

输入 #1

3 3 1

输出 #1

4

输入 #2

4 2 1

输出 #2

9

输入 #3

5 5 4

输出 #3

120

输入#4

100 1 2

输出#4

100

注意

在第一个示例中,Neko 可以通过 $$$4$$$ 方式访问所有行星:

- $$$1 \右箭头 2 \右箭头 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 可以访问所有行星的方式。

在第四个例子中,Neko 只访问了 $$$1$$$ 星球(这也是他最初定位的星球),并且有 $$$100$$$ 方法来选择 Neko 的起始星球。