Polygon Dissection Count

Time limit2sMemory limit128 MB

Summary

Given a convex N-gon, count the number of ways to cut it with non-crossing diagonals into exactly K polygons, modulo 1000000000, or report impossibility.

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

Problem

Sejun has a convex polygon with N distinct vertices. One cut must connect two vertices of the current polygon, and the cut is valid only when it divides one polygon into exactly two polygons.

Write a program that counts how many different ways there are to divide the convex N-gon into exactly K polygons.

Input

The first line contains two integers N and K.

3 <= N <= 100
1 <= K <= 100

Output

Print the number of valid divisions modulo 1000000000.

If it is impossible to divide the N-gon into exactly K polygons, print -1.

Examples5

Example 1
Input
```
6 4
```
Expected output
```
14
```
Example 2
Input
```
4 2
```
Expected output
```
2
```
Example 3
Input
```
100 1
```
Expected output
```
1
```
Example 4
Input
```
31 20
```
Expected output
```
956146480
```
Example 5
Input
```
3 4
```
Expected output
```
-1
```