Circular Ball Passing Game

During a physical education class, students stand in a circle. Initially, Xiaoman holds a ball. When the teacher blows the whistle, the ball is passed; each student may pass the ball to the neighbor on the left or right. After exactly m passes, if the ball returns to Xiaoman, the passing sequence is considered valid. Two passing sequences are different if the sequence of ball receivers (in order) differs.

This problem asks: given n students arranged in a circle (numbered modulo n) and an integer m, how many different passing sequences starting from Xiaoman (position 0) will result in the ball returning to Xiaoman after exactly m passes?

Mathematically, if we represent a pass as either a step of +1 (clockwise) or -1 (counter-clockwise) on the circle, then we need to count the number of sequences of m moves such that the cumulative sum is congruent to 0 modulo n. For example, when n = 3 and m = 3, there are exactly 2 valid sequences:

$1 \rightarrow 2 \rightarrow 3 \rightarrow 1$
$1 \rightarrow 3 \rightarrow 2 \rightarrow 1$

inputFormat

The input consists of a single line with two integers n and m separated by spaces, where:

• n is the number of students arranged in a circle.
• m is the number of times the ball is passed.

Note: You may assume that n and m are small enough for a dynamic programming solution to run in time.

outputFormat

Output a single integer representing the number of different passing sequences that start with Xiaoman and return to her after exactly m passes.

sample

3 3

2