Problem Description

Today is Christmas Eve. Paken wants to create a decoration for the last Christmas of the Heisei era, which consists of "lights" and "rods". The decoration is created as follows:

• Create light bulbs $ (a, b) $ ($0 \leq a \leq D, -a \leq b \leq a$, where $a$ and $b$ are integers). $a$ is called the "depth" and $b$ is called the "horizontal coordinate".
• Connect light bulbs $ (0, 0) $ and $ (1, -1) $, and light bulbs $ (0, 0) $ and $ (1, 1) $ directly with rods.
• Connect light bulbs with the same depth and a horizontal coordinate difference of 1 directly with rods.
• Connect light bulbs $ (a, -(a-1)) $ and $ (a+1, -(a+1)) $, and light bulbs $ (a, a-1) $ and $ (a+1, a+1) $ directly with rods.

For example, when $ D = 1, 2, 3 $, the graph looks like the following:

It seems like a Christmas tree.

Paken wants to color all the light bulbs using $ X $ colors from color 1 to color $ X $. However, light bulbs directly connected by rods must not have the same color.
Find the number of ways to color the light bulbs, modulo $ 1,000,000,007 $.

Input Format

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

$ D $ $ X $

Output Format

Output the number of ways to color the light bulbs, modulo $ 1,000,000,007 $, in one line.

Sample Input and Output

Sample Input #1

1 2

Sample Output #1

2

Sample Input #2

1 3

Sample Output #2

18

Sample Input #3

4 5

Sample Output #3

101969466

Notes/Hints

Constraints

• $ D $ is an integer between 1 and $ 10,000,000 $ inclusive.
• $ X $ is an integer between 1 and $ 1,000,000,000 $ inclusive.

Subtasks

Subtask $ 1 $ [$ 2 $ points]

The input satisfies the following conditions:

• $ D = 1 $
• $X \leq 4$

Subtask $ 2 $ [$ 12 $ points]

The input satisfies the following conditions:

• $D \leq 2$
• $X \leq 6$

Subtask $ 3 $ [$ 21 $ points]

The input satisfies the following conditions:

• $D \leq 4$
• $X \leq 7$

Subtask $ 4 $ [$ 31 $ points]

The input satisfies the following conditions:

• $D \leq 50$
• $X \leq 25$

Subtask $ 5 $ [$ 18 $ points]

• $D \leq 50$

Subtask $ 6 $ [$ 11 $ points]

• $D \leq 100,000$

Subtask $ 7 $ [$ 5 $ points]

• No additional constraints.

Sample Explanation 1

There are $ 2 $ ways to color the light bulbs as follows:

Sample Explanation 2

There are $ 18 $ ways to color the light bulbs as follows: This input satisfies the constraints of Subtask $ 1 $.

Sample Explanation 3

This input does not satisfy the constraints of Subtask $ 2 $ but satisfies the constraints of Subtask $ 3 $.

见题面 Input 部分

见题面 Output 部分