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
hide comments
Michael Kharitonov:
20130310 12:06:03
After you solved this easy dynamic programming task look at hard version:


Francky:
20130302 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:  20091221 
Time limit:  0.582s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 