14276번 - 도로 건설

문제

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

• 서로 다른 집 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의 경우 아래와 같이 도로를 건설하는 것이 가능하다.

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