Eel and Grid

Time limit1sMemory limit256 MB

Summary

An eel on a toroidal H by W grid walks right or down, painting cells, until it returns to a painted cell; count Hamiltonian-style walks that cover every cell and end at (0,0).

Level: Hard8 of 10
Topics: Combinatorics, Math, Dynamic programming
Solved: No attempts yet

Problem

There is an $H \times W$ grid. Let $(i,\ j)$ be the cell at the intersection of the $i$ -th row ( $0 \leq i \leq H-1$ ) and the $j$ -th column ( $0 \leq j \leq W-1$ ). Initially, an eel is at cell $(0,\ 0)$ . The eel repeats the following process.

If the current cell is painted, end the process.
If the current cell is not painted, paint the cell and move to another cell. If the current cell is $(i,\ j)$ , the new cell must be either $((i+1)\ {\rm mod}\ H,\ j)$ or $(i,\ (j+1)\ {\rm mod}\ W)$ .

Count the number of ways to paint all cells and end the process at cell $(0,\ 0)$ , modulo $10^9+7$ . Two ways are considered distinct if the paths traveled by the eel are distinct.

Input

$H$ $W$

Output

Print the answer modulo $10^9+7$ .

Constraints

$2 \leq H, W \leq 10^6$

Hint

The following picture shows the two ways in Sample 1:

Examples5

Example 1
Input
```
2 2
```
Expected output
```
2
```
Example 2
Input
```
6 3
```
Expected output
```
3
```
Example 3
Input
```
3 4
```
Expected output
```
0
```
Example 4
Input
```
10 10
```
Expected output
```
260
```
Example 5
Input
```
200 300
```
Expected output
```
551887980
```