Problem Description

There are $ N $ buildings with $ M $ floors each. Ninja Takahashi has decided to infiltrate all floors of all buildings. Initially, Takahashi is on the 1st floor of the 1st building and wants to return to the 1st floor of the 1st building eventually.

Takahashi can make the following two types of moves:

• Move to an adjacent floor in the same building using stairs.
• Teleport to the same floor of a different building.

Since staying in a building for too long might get him caught, he wants to return to the 1st floor of the 1st building without entering the same floor of the same building more than once.

Find the number of ways to make these moves, modulo $ 10^9+7 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $

Output Format

Output the total number of ways to make the moves, modulo $ 10^9+7 $.

Sample Input and Output

Sample Input #1

3 2

Sample Output #1

6

Sample Input #2

98 7654321

Sample Output #2

257361229

Notes/Hints

Constraints

• $2 \leq N \leq 100$
• $2 \leq M \leq 10^9$
• All inputs are integers.

Sample Explanation 1

There are 6 possible ways. $ (i,j) $ represents the $ j $th floor of the $ i $th building.

• $(1,1) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (1,1)$
• $(1,1) \rightarrow (3,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (1,2) \rightarrow (1,1)$
• $(1,1) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,1) \rightarrow (1,1)$
• $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,1) \rightarrow (2,1) \rightarrow (1,1)$
• $(1,1) \rightarrow (1,2) \rightarrow (3,2) \rightarrow (2,2) \rightarrow (2,1) \rightarrow (3,1) \rightarrow (1,1)$
• $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (1,2) \rightarrow (3,2) \rightarrow (3,1) \rightarrow (1,1)$

见题面 Input 部分

见题面 Output 部分