DTPOLY - Divide Polygon

Determine the number of ways to cut a convex polygon with N sides if the only cuts allowed are from vertex to vertex, each cut divides exactly one polygon into exactly two polygons, and you must end up with exactly K polygons. Consider each vertex distinct. For example, there are three ways to cut a square - the two diagonals and not cutting at all - but only two ways to cut it to form 2 polygons, and only one way to cut it to form 1 polygon. The order of cuts does not matter. Since the number of ways is very large, you should return the number taken modulo 1000000000 (one billion). If there is no way to cut the polygon into K pieces, return -1.    

Input

  • Input contains only 2 integers in one line: N (1 ≤ N ≤ 100) and K (1 ≤ K ≤ 100).

Output

  • Output contains only one integer, the number of different ways to cut the polygon into K pieces.

Example

Input:
4 2

Output:
2

Added by:khanhptnk
Date:2009-12-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6

hide comments
2013-03-10 12:06:03 Michael Kharitonov
After you solved this easy dynamic programming task look at hard version:
http://www.spoj.com/problems/DTPOLY2/
2013-03-02 17:05:24 Francky
There's a problem with input here, Python users will use sys, read and strip. It's possible that in some files the numbers are on separate lines or another issue...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.