这个问题与下一个问题相同,但约束较小。
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 的起始星球。