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.