Let's consider a regular polygon on the plane with n vertices, numbered from 0 to n-1, inclusive. The polygon's n-3 diagonals are called a *triangulation* if no two diagonals intersect at a point strictly inside the polygon. Two triangulations A and B are considered to be distinct if there are two vertices i and j such that A contains the diagonal between vertices i and j, and B doesn't contain this diagonal.
It's not hard to see that every triangulation breaks the polygon into n-2 triangles. The triangulation is called *k-isosceles*, if there are exactly k isosceles triangles among them. Given ints **n** and **k**, compute the number of distinct **k**-isosceles triangulations of a regular polygon with **n** vertices. Return the result modulo 123456789. |