Polygon Dissection Count

Time limit

Memory limit

128 MB

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.