Consider tables with $N$ rows and $M$ columns containing only the numbers $0$ and $1$. A table is good if every row contains either one or two ones, and every column also contains either one or two ones. Determine the remainder of the number of good tables with $N$ rows and $M$ columns when divided by $10^9 + 7$.
Input
The first line contains the natural numbers $N$ and $M$.
Output
In a single line, print the remainder of the number of good tables when divided by $10^9 + 7$.
Subtasks
In all subtasks, $1 \le N, M \le 3000$.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 10 | $N, M \le 6$ |
| 2 | 18 | $N, M \le 50$ |
| 3 | 31 | $N, M \le 200$ |
| 4 | 41 | No additional constraints. |
Examples
Input 1
2 2
Output 1
7
Note
Explanation of the first example:
All good tables with 2 rows and 2 columns:
0 1 1 0 0 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1
Input 2
3 3
Output 2
102
Input 3
15 20
Output 3
415131258