Dinamo

Task

Due to the positive reviews received by the committee regarding a certain problem involving tiling on matrices, we present the following problem:

A tile is called a ketris tile if:

• It has a rectangular shape, and the lengths of its sides (in meters) are natural numbers.
• At least one of its sides has a length of $1$ meter.

A complete coverage of a surface with ketris tiles is called a ketris tiling.

How many ketris tilings exist for a rectangular surface with side lengths of $n$ and $m$ meters? Since the answer can be very large, print the result modulo $10^9+7$.

Two ketris tilings are considered different if there exists a ketris tile that appears in the first tiling in a certain location but not in the second.

Input data

The first line of the input file contains two natural numbers $n$ and $m$ - the height and width of the surface, respectively.

Output data

Print the number of possible ketris tilings. Since the answer can be very large, print it modulo $10^9+7$.

Constraints and clarifications

• $1 \le n \le 10$
• $1 \le m \le 10^{18}$

Example 1

stdin

1 4

stdout

8

Explanation

There are $8$ possible ketris tilings:

Example 2

stdin

2 2

stdout

7

Explanation

There are $7$ possible ketris tilings:

Example 3

stdin

2 3

stdout

29

Example 4

stdin

2 11

stdout

3381689

Example 5

stdin

6 5

stdout

441987135

Example 6

stdin

7 420

stdout

496377800