Road Construction

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.

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

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

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.