Neko Rules the Catniverse (Small Version)
Contest: Codeforces Round 554 (Div. 2)
Difficulty rating: 2800
Tags: bitmasks, dp, matrices

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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3 3 1

Example output:
4

Example input:
4 2 1

Example output:
9

Editorial:
As the problem stated, from planet $$$x$$$ we can go backwards any to any planet $$$y$$$ such that $$$y < x$$$.
This implies an idea of considering the planets from $$$n$$$ to $$$1$$$, then deciding whether to insert each planet to the current path or not.
Formally, if our current path is $$$v_1, v_2, \dots, v_p$$$ and we are going to insert planet $$$x$$$ somewhere ($$$x < v_i$$$ for all $$$i$$$), we can either insert it into the back, or insert it before some planet $$$v_i$$$ such that $$$v_i \le x + m$$$.
Therefore, we can use dynamic programming with the parameters being: the planet being considered, the number of planets chosen so far, and the bitmask of the last $$$m$$$ planets (whether each of them is chosen or not).
The transition is straightforward: either we don't choose the planet, or we choose it and there are $$$1 + bitcount(mask)$$$ ways to insert the planet into the path.
Total complexity: $$$\mathcal{O} \left( nk \cdot 2^m \right)$$$.