Chocolate triangles

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

요약

볼록 n각형을 서로 교차하지 않는 대각선으로 정확히 k개의 삼각형으로 자르는 방법의 수를 1e9+9로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 조합론, 수학, 구간
정답자: 아직 제출이 없습니다

문제

"Tortoff" Inc. makes your favorite chocolate products. For your convenience we produce chocolate exclusively in the shape of convex polygon. You can break it into pieces along any non-intersecting diagonals. According to our expert surveys the tastiest pieces of chocolate are triangular. Any customer can help us improve the quality of our products. It is important for us to know the number of ways our exclusive chocolate can be broken into exactly $k$ triangular parts.

입력

Single line contains integers $n$ and $k$ ( $3 \le n \le 300$ , $0 \le k \le n-2$ ).

출력

Output the number of ways the $n$ -polygon can be cut into exactly $k$ triangular parts along non-intersecting diagonals inside the polygon. Output answer modulo ( $10^9 + 9$ ).

예제3

예제 1
입력
```
4 0
```
예상 출력
```
1
```
예제 2
입력
```
4 1
```
예상 출력
```
0
```
예제 3
입력
```
4 2
```
예상 출력
```
2
```