Coco is playing Tic-Tac-Toe with Hanbyeol using white and dark chocolates. The rules of Tic-Tac-Toe are as follows:

• Prepare a game board with a $3 \times 3$ grid.
• Two players take turns placing a chocolate in an empty cell on the board. The first player places white chocolate, and the second player places dark chocolate. A chocolate cannot be placed in a cell that is already occupied.
• The player who first places 3 chocolates of the same color in a horizontal, vertical, or diagonal line wins. If the board is full and no one has won, the game is a draw.

Coco grew bored of the game always ending in a draw and began to wonder: if two people cooperate to create a drawn game on an $N \times M$ board, how many different game boards can result? Let's help Coco solve this. Even if the board size changes, a player wins if they place 3 consecutive chocolates in a horizontal, vertical, or diagonal line.

Two game boards are considered different if there is at least one cell with a different chocolate at the same coordinate. If the final positions of the chocolates are identical, the boards are considered the same, regardless of the order in which the chocolates were placed. "Diagonal" refers only to the 45-degree directions (down-right and up-right).

(Explanation for Example 1)

There are 16 possible drawn game boards on a $3 \times 3$ board, as shown below:

Input

The integers $N$ and $M$ are given on the first line. ($1 \le N, M \le 1000$)

Output

Output the number of different drawn game boards that can result from a Tic-Tac-Toe game on an $N \times M$ board, modulo $10^9+7$.

Examples

Input 1

3 3

Output 1

16