402045: GYM100633 C Chocolate triangles

"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 ≤ n ≤ 300, 0 ≤ k ≤ 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).

4 0

1

4 1

0

4 2

2