2014
02-27

# XX’s puzzle

XX and QQ are good friends. Some few months ago, XX always sat beside QQ and they always talked about some hard programming problems and also sometimes played StarCraft (∩_∩). XX likes playing Protoss while QQ likes playing Terran, and XX is a perfect player and courage QQ to win the others. But now, XX has gone to ZJU to study master, so QQ always thinks of him. XX is a mischievous boy, and he invariably comes up with lots of hard problems to challenge QQ, but fails at the most time. In the recent days, XX finds a problem which he regards as a very puzzling problem. Being surprised by QQ’s skill, XX is determined to let you solve this problem and tests whether the problem is enough puzzling, the problem is described:
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 integer n and k, compute the number of distinct k-isosceles triangulations of a regular polygon with n vertices. Return the result modulo 9397.

There are many test cases.
For every case, there are two nonnegative integer n and k, 3<=n<=50, 0<=k<=n-2;

There are many test cases.
For every case, there are two nonnegative integer n and k, 3<=n<=50, 0<=k<=n-2;

4 2
3 0
5 3 

2
0
5
Hint
Hint:
For the first case, we can have a diagonal between vertices 0 and 2 or between vertices 1 and 3. In both cases, there are 2 isosceles triangles.
For the second case, the only triangulation of an equilateral triangle contains no diagonals and 1 isosceles triangle (the polygon itself).
For the third case, a regular pentagon has 5 triangulations.
Each of them is obtained by connecting one selected vertex with the two others that are not its neighbors, so each triangulation is 3-isosceles.