초콜릿 삼각형

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

요약

볼록 n각형을 서로 교차하지 않는 대각선으로 잘랐을 때 정확히 k개의 조각이 삼각형이 되는 방법의 수를 10^9+9로 나눈 나머지로 구합니다.

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

문제

"Tortoff" 주식회사는 여러분이 좋아하는 초콜릿 제품을 만듭니다. 편의를 위해 이 회사는 볼록 다각형 모양의 초콜릿만 생산합니다. 초콜릿은 서로 교차하지 않는 임의의 대각선을 따라 조각으로 나눌 수 있습니다. 전문가 설문에 따르면 가장 맛있는 조각은 삼각형입니다. 고객은 누구나 제품 품질 향상에 도움을 줄 수 있습니다. 회사는 이 초콜릿을 정확히 $k$ 개의 삼각형 조각으로 나누는 방법이 몇 가지인지 알고 싶어 합니다.

입력

한 줄에 정수 $n$ 과 $k$ 가 주어집니다 ( $3 \le n \le 300$ , $0 \le k \le n-2$ ).

출력

$n$ 각형을 다각형 내부에서 서로 교차하지 않는 대각선을 따라 정확히 $k$ 개의 삼각형 조각으로 나누는 방법의 수를 $10^9 + 9$ 로 나눈 나머지로 출력합니다.

예제3

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