{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e这个问题与下一个问题相同,但约束条件更小\u003c/span\u003e。\u003c/p\u003e\u003cp\u003eAki正在玩一个新的视频游戏。在这个视频游戏中,他将控制巨大的猫Neko在猫星球之间飞行。\u003c/p\u003e\u003cp\u003e猫星球中有$$$n$$$颗行星,编号从$$$1$$$到$$$n$$$。在游戏开始时,Aki选择Neko最初所在的行星。然后Aki执行$$$k - 1$$$次移动,每次移动中Neko从当前行星$$$x$$$移动到另一行星$$$y$$$,满足以下条件:\u003c/p\u003e\u003cul\u003e \u003cli\u003e 行星$$$y$$$尚未被访问。 \u003c/li\u003e\u003cli\u003e $$$1 \\leq y \\leq x + m$$$(其中$$$m$$$是输入中给定的固定常数) \u003c/li\u003e\u003c/ul\u003e\u003cp这样,Neko将恰好访问$$$k$$$个不同的行星。如果两种访问行星的方式不同,则称为不同,如果存在某个索引$$$i$$$,则第一种方式中第$$$i$$$个访问的行星与第二种方式中第$$$i$$$个访问的行星不同。\u003c/p\u003e\u003cp以这种方式访问$$$k$$$个行星的总方式数是多少?由于答案可能非常大,因此对$$$10^9 + 7$$$取模后输出。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e仅一行包含三个整数$$$n$$$、$$$k$$$和$$$m$$$($$$1 \\le n \\le 10^5$$$、$$$1 \\le k \\le \\min(n, 12)$$$、$$$1 \\le m \\le 4$$$)— 猫星球中的行星数,Neko需要访问的行星数以及所述常数$$$m$$$。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个整数 — Neko可以访问恰好$$$k$$$个行星的不同方式数。由于答案可能非常大,因此对$$$10^9 + 7$$$取模后输出。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 5 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e120\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e100 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e100\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,Neko可以访问所有行星的方式有$$$4$$$种:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\rightarrow 2 \\rightarrow 3$$$ \u003c/li\u003e\u003cli\u003e $$$2 \\rightarrow 3 \\rightarrow 1$$$ \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 1 \\rightarrow 2$$$ \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 2 \\rightarrow 1$$$ \u003c/li\u003e\u003c/ul\u003e\u003cp在第二个示例中,Neko可以访问恰好$$$2$$$个行星的方式有$$$9$$$种:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1 \\rightarrow 2$$$ \u003c/li\u003e\u003cli\u003e $$$2 \\rightarrow 1$$$ \u003c/li\u003e\u003cli\u003e $$$2 \\rightarrow 3$$$ \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 1$$$ \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 2$$$ \u003c/li\u003e\u003cli\u003e $$$3 \\rightarrow 4$$$ \u003c/li\u003e\u003cli\u003e $$$4 \\rightarrow 1$$$ \u003c/li\u003e\u003cli\u003e $$$4 \\rightarrow 2$$$ \u003c/li\u003e\u003cli\u003e $$$4 \\rightarrow 3$$$ \u003c/li\u003e\u003c/ul\u003e\u003cp在第三个示例中,对于$$$m \u003d 4$$$,Neko可以以任意顺序访问所有行星,因此Neko可以访问所有行星的方式有$$$5! \u003d 120$$$种。\u003c/p\u003e\u003cp在第四个示例中,Neko只能访问恰好$$$1$$$个行星(也是他最初所在的行星),选择Neko的起始行星有$$$100$$$种方式。\u003c/p\u003e"}}]}