피루에트

시간 제한1초메모리 제한1024 MB

요약

가운데 0에서 출발해 한 칸씩 T걸음을 걷는 발레리나가 T걸음 뒤 다시 0에 서도록 장애물 K개를 놓는 방법의 수를 구합니다. 장애물에 부딪히면 방향을 바꾸고 장애물은 사라집니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 조합론, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

정수 $N$ 이 주어진다. 구간 $[-N-1, N+1]$ 로 나타나는 길이 $2 \times N+2$ 의 방을 생각하자. 방의 중앙 $C=0$ 에는 Costelina Salopeta라는 발레리나가 있다. 그녀는 길이가 $1$ 인 춤 동작을 $T$ 번 수행한다. 첫 동작은 오른쪽으로 이동하는 것이다. 방에는 $2 \times N$ 개의 정수 좌표가 있고, 그중 $K$ 개의 좌표에 장애물을 놓을 수 있다. 발레리나가 장애물에 닿으면 발이 걸려 피루에트를 한다. 그러면 이동 방향이 바뀌고, 그 장애물은 사라진다.

좌표 $-N-1$ , $0$ , $N+1$ 에는 장애물을 놓을 수 없다. 좌표 $-N-1$ 과 $N+1$ 의 벽은 사라지지 않는 영구 장애물이다. 점 $C=0$ 은 발레리나의 시작 위치이다.

$T$ , $N$ , $K$ 가 주어졌을 때, $T$ 번 이동한 뒤 발레리나가 출발점 $C$ 로 돌아오도록 $K$ 개의 장애물을 놓는 방법의 수를 구하라.

입력

첫 번째 줄에 정수 $T$ , $N$ , $K$ 가 주어진다.

출력

답을 $10^9+7$ 로 나눈 나머지를 정수 하나로 출력한다.

제한

$0 \le T \le 200$ , $T$ 는 짝수이다.
$1 \le N \le 100$
$0 \le K \le 2 \times N$

예제2

예제 1
입력
```
6 3 4
```
예상 출력
```
7
```
예제 2
입력
```
8 3 1
```
예상 출력
```
3
```