영선이가 살고있는 도시에는 총 N개의 집이 있고, 1번부터 N번까지 번호가 매겨져 있다. 현재 도시에 도로는 하나도 없다. 영선이는 아래 조건을 지키면서 총 M개의 양방향 도로(집과 집을 연결)를 만들려고 한다.</p>

• 서로 다른 집 A와 B에 대해서, 0 < |A-B| ≤ K인 경우에만 도로를 만들 수 있다. 도로로 연결되어 있는 집은 도로와 인접해있다고 한다. 같은 집의 쌍에 대해서 여러 개의 도로를 만들 수 있다.
• 모든 집은 짝수개의 도로와 인접해야 있어야 한다.

N, M, K가 주어졌을 때, 도로를 만드는 방법의 수를 구하는 프로그램을 작성하시오. 두 집이 서로 다른 개수의 도로와 연결되어 있을 때 두 방법을 서로 다른 방법이라고 한다.

입력 형식

첫째 줄에 N, M, K (1 ≤ N ≤ 30, 0 ≤ M ≤ 30, 1 ≤ K ≤ 8)이 주어진다.

출력 형식

첫째 줄에 도로를 만드는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다.

예제 입력 1

3 4 1

예제 출력 1

3

예제 입력 2

4 3 3

예제 출력 2

4

예제 입력 3

2 1 1

예제 출력 3

0

예제 입력 4

5 0 3

예제 출력 4

1

예제 입력 5

10 20 5

예제 출력 5

26964424

힌트

예제 1의 경우 아래와 같이 도로를 건설하는 것이 가능하다.</p>

예제 2의 경우 아래와 같이 도로를 건설하는 것이 가능하다.