Road Construction

Time limit2sMemory limit512 MB

Summary

Count the ways to place exactly M undirected edges among N houses, each edge joining houses at distance at most K, so that every house has even degree, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Graph, Bit manipulation
Solved: No attempts yet

Problem

Yeongseon lives in a city with $N$ houses, numbered 1 to $N$ . The city has no roads at the moment. Yeongseon wants to build exactly $M$ two-way roads between houses while keeping both rules below.

Two different houses $A$ and $B$ can be joined by a road only when $0 < |A - B| \le K$ . Two houses joined by a road are adjacent. Several roads can join the same pair of houses.
Every house must be adjacent to an even number of roads.

Two plans count as different when some pair of houses is joined by a different number of roads. Given $N$ , $M$ and $K$ , write a program that counts the plans for building the roads.

Input

The first line contains $N$ , $M$ and $K$ . ( $1 \le N \le 30$ , $0 \le M \le 30$ , $1 \le K \le 8$ )

Output

Print the number of plans for building the roads, modulo 1,000,000,007, on the first line.

Hint

The picture below shows one way to build the roads in the first example.

The picture below shows one way to build the roads in the second example.

Examples5

Example 1
Input
```
3 4 1
```
Expected output
```
3
```
Example 2
Input
```
4 3 3
```
Expected output
```
4
```
Example 3
Input
```
2 1 1
```
Expected output
```
0
```
Example 4
Input
```
5 0 3
```
Expected output
```
1
```
Example 5
Input
```
10 20 5
```
Expected output
```
26964424
```