Description

During PE class, Xiaoman’s teacher often plays games with the students. This time, the teacher is leading a passing game.

The rules are as follows: $n$ students stand in a circle. One student holds a ball at the start. When the teacher blows the whistle, the passing begins. Each student can pass the ball to either of their two neighbors (left or right, chosen arbitrarily). When the teacher blows the whistle again, the passing stops. At that moment, the student holding the ball, who has not passed it on, is the loser and must perform a show for everyone.

Xiaoman提出了一个有趣的问题: In how many different ways can the ball, starting from Xiaoman, return to Xiaoman after $m$ passes? Two passing methods are considered different if and only if the sequences of students who receive the ball, in the order they receive it, are different. For example, with three students numbered $1$, $2$, and $3$, and assuming Xiaoman is number $1$, there are $2$ ways for the ball to return to Xiaoman after $3$ passes: $1 \rightarrow 2 \rightarrow 3 \rightarrow 1$ and $1 \rightarrow 3 \rightarrow 2 \rightarrow 1$.

Input Format

One line with two space-separated integers $n,m(3 \le n \le 30,1 \le m \le 30)$.

Output Format

$1$ integer, representing the number of valid methods.

3 3

2

Hint

Constraints and Conventions

• For $40\%$ of the testdata, it holds that: $3 \le n \le 30,1 \le m \le 20$.
• For $100\%$ of the testdata, it holds that: $3 \le n \le 30,1 \le m \le 30$.

Third problem of the 2008 Junior.

Translated by ChatGPT 5