Description

Xiaoyu learned from a history book about an ancient civilization. This civilization was highly developed in every aspect, including transportation. Archaeologists already know that, at its peak, the civilization had $n$ cities, numbered $1,2,...,n$. There were $m$ roads connecting these cities. Each road connects two cities, making it convenient for residents to travel between them. There may be multiple roads between the same pair of cities.

According to historical records, the transportation network of this civilization satisfied two strange properties.

1. This civilization worshipped the number $k$. For any road, suppose the two cities it connects are $u$ and $v$. Then it must satisfy $1 \le \left\vert {u-v}\right\vert \le k$.
2. Every city is connected to exactly an even number of roads (and $0$ is also considered even).

However, because so much time has passed, we can no longer know the exact transportation network. Xiaoyu is very curious about how many possible ways these $n$ cities could be connected, so she asks you for help.

Two possible connection methods are different if and only if there exists a pair of cities such that the number of roads between them is different in the two methods.

In the transportation network, it is possible that some cities cannot reach each other.

The number of methods may be very large. You only need to output the result modulo $10^9 + 7$.

Input Format

The input consists of one line with three integers $n,m,k$.

Output Format

Output one integer, the number of valid methods modulo $10^9 + 7$.

3 4 1

3

4 3 3

4

Hint

Constraints

• For $100\%$ of the testdata, $1 \le n,m \le 30$, $1 \le k \le 8$.

Translated by ChatGPT 5