Chocolate triangles

Time limit4sMemory limit1024 MB

Summary

Count the ways to cut a convex n-gon along non-crossing diagonals so that exactly k of the resulting pieces are triangles, modulo 1e9+9.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

"Tortoff" Inc. makes your favorite chocolate products. For your convenience, it produces chocolate only in the shape of a convex polygon. You can break the chocolate into pieces along any diagonals that do not intersect. Expert surveys show that the tastiest pieces are triangular. Any customer can help improve the quality of the products. The company needs to know how many ways its chocolate can be broken into exactly $k$ triangular parts.

Input

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

Output

Print the number of ways to cut the $n$ -gon into exactly $k$ triangular parts along non-intersecting diagonals inside the polygon, modulo $10^9 + 9$ .

Examples3

Example 1
Input
```
4 0
```
Expected output
```
1
```
Example 2
Input
```
4 1
```
Expected output
```
0
```
Example 3
Input
```
4 2
```
Expected output
```
2
```