Background

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

Problem Description

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.

Input Format

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

Output Format

Output $1$ integer, the number of methods that satisfy the requirement.

Since the answer may be very large, output it modulo $10^9+7$.

3 3

2

30 30

155117522

1234 12345678

424074635

Hint

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