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.