P5173 Passing the Ball

As the middle school entrance exam is approaching, pG’s head teacher decides to hold a PE class to help everyone relax.

The teacher leads pG’s classmates to play a ball-passing game. The rules are as follows: $n$ students stand in a circle. One of them holds a ball at the beginning. When the teacher blows the whistle, they start passing the ball. Each student can pass the ball to either of their two neighbors (left or right, either is allowed). When the teacher blows the whistle again, passing stops. At that moment, the student who is holding the ball and did not pass it out is the loser, and must perform a show for everyone. pG asks an interesting question: how many different passing methods make it so that the ball, starting from pG, returns to pG after being passed $m$ times? Two passing methods are considered different if and only if the sequence of students who receive the ball (in the order of receiving) is different. For example, if there are three students numbered $1$, $2$, $3$, and pG is student $1$, then the ways for the ball to return to pG after $3$ passes are $1 \to 2 \to 3 \to 1$ and $1 \to 3 \to 2 \to 1$, for a total of $2$ ways.

One line containing two integers $n, m$ separated by a space.

Output $1$ integer, the number of methods that satisfy the requirement. Since the answer may be very large, output it modulo $10^9+7$.

For $8\%$ of the testdata, $n \le 100, m \le 10^4$. For $100\%$ of the testdata, $n \le 3500, m \le 10^9$. **The testdata has a certain gradient.** Translated by ChatGPT 5