Description

As is well known, a canon is a polyphonic composition technique. While listening to canons, Xiao Yu had a burst of inspiration and invented a new rule for writing music.

He divides the sounds into $n$ notes and splits the music into several segments. Each segment is a harmony composed of $1$ to $n$ notes, i.e., selecting some of the $n$ notes to play simultaneously.

To distinguish it from canons, he stipulates that the set of notes contained in any two segments must be different. To maintain regularity, he also requires that in one piece of music each note is sounded an even number of times across all segments.

Now the question is: how many pieces of music consisting of $m$ segments are there? Two pieces of music $a$ and $b$ are considered the same if and only if $b$ can be obtained by reordering the segments of $a$. For example, suppose $a$ is $\{\{1,2\},\{2,3\}\}$ and $b$ is $\{\{2,3\},\{1,2\}\}$, then $a$ and $b$ are the same music.

The answer should be taken modulo $10^8+7$.

Input Format

One line containing two positive integers $n, m$.

Output Format

Output one line with a single integer representing the answer.

2 3

1

Hint

Constraints
For $20\%$ of the testdata, $1 \le n, m \le 5$.
For $50\%$ of the testdata, $1 \le n, m \le 3000$.
For $100\%$ of the testdata, $1 \le n, m \le 10^6$.

Sample Explanation
The music is $\{\{1\},\{2\},\{1,2\}\}$.

Translated by ChatGPT 5