Problem Statement 
 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). In other words, if the answer would have at least 10 digits, return only the 9 least significant. If there is no way to cut the polygon into k pieces, return 1. 

Definition 
 Class:  PolygonDecomposition  Method:  howMany  Parameters:  int, int  Returns:  int  Method signature:  int howMany(int n, int k)  (be sure your method is public) 




Notes 
  The vertices are distinct  there are 5 ways to cut a pentagon into 3 triangles, not just one way. 
  Only one polygon at a time may be cut  you cannot cut two triangles into four triangles with one cut. 

Constraints 
  n is between 3 and 100, inclusive. 
  k is between 1 and 100, inclusive. 

Examples 
0)  
  Returns: 2  A quadrilateral can be cut into two triangles in two different ways, one for each diagonal. 


1)  
  Returns: 1  Any polygon can be cut into one polygon by not cutting at all, but no other way. 


2)  
 
3)  
  Returns: 956146480  The actual number of ways is about 6.5 x 10^18, but we return only the final 9 digits. 


4)  
 