Problem Background

Imakf has grown tired of playing international chess and decides to try Chinese chess. He notices that the horses in Chinese chess are different from those in international chess. Realizing this could lead to another simple problem, he prepares to place some horses on the board.

Problem Description

Imakf has a chessboard with $X$ rows and $Y$ columns, and he has many identical horses (you can assume there are infinitely many). He wants to place horses on the board (or not place any) such that no horse can attack another horse. Calculate the total number of such arrangements.

The horses in Chinese chess move differently from those in international chess.

Note: There are no pawns in the actual problem.

Since the number of arrangements might be very large, output the result modulo $(10^9 + 7)$.

Input Format

The first line contains two positive integers $X$ and $Y$.

Output Format

Output the number of arrangements modulo $(10^9 + 7)$.

Sample Input and Output

Sample Input #1

1 1

Sample Output #1

2

Sample Input #2

3 3

Sample Output #2

145

Notes/Hints

For 100% of the data, $1 \leq X \leq 100$ and $1 \leq Y \leq 6$.

For 20% of the data, $X, Y \leq 6$.

For another 20% of the data, $X \leq 20$.

For Sample 1, the options are to place no horse or one horse.

For Sample 2, I have a wonderful explanation, but there's not enough space to write it.

见题面 Input 部分

见题面 Output 部分