DTPOLY - Divide Polygon

no tags 

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

hide comments
Michael Kharitonov: 2013-03-10 12:06:03

After you solved this easy dynamic programming task look at hard version:
http://www.spoj.com/problems/DTPOLY2/

Francky: 2013-03-02 17:05:24

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


Added by:Nguyễn Xuân Khánh
Date:2009-12-21
Time limit:0.582s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6