19523번 - Eel and Grid 다국어

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, there is an eel at the 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 the cell $(0,\ 0)$, modulo $10^9+7$. Two ways are considered distinct if the path traveled by the eel are distinct.

$H$ $W$

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

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

The following picture shows the two ways in Sample 1: