402045: GYM100633 C Chocolate triangles

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Chocolate trianglestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

"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.

Input

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

Output

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 (109 + 9).

ExamplesInput
4 0
Output
1
Input
4 1
Output
0
Input
4 2
Output
2

加入题单

上一题 下一题 算法标签: