뱀장어와 격자

시간 제한1초메모리 제한256 MB

요약

토러스 모양의 H×W 격자에서 뱀장어가 오른쪽이나 아래로만 움직이며 칸을 칠하다가 이미 칠한 칸에 도달하면 멈춘다. 모든 칸을 칠하고 (0,0)에서 끝나는 경로의 수를 세는 문제다.

난이도: 어려움10점 중 8점
유형: 조합론, 수학, 동적 계획법
정답자: 아직 제출이 없습니다

문제

$H \times W$ 격자가 있다. $i$ 번째 행( $0 \leq i \leq H-1$ )과 $j$ 번째 열( $0 \leq j \leq W-1$ )이 만나는 칸을 $(i,\ j)$ 라 하자. 처음에 뱀장어가 칸 $(0,\ 0)$ 에 있다. 뱀장어는 다음 과정을 반복한다.

현재 칸이 칠해져 있으면 과정을 끝낸다.
현재 칸이 칠해져 있지 않으면 그 칸을 칠하고 다른 칸으로 이동한다. 현재 칸이 $(i,\ j)$ 라면 새 칸은 $((i+1)\ {\rm mod}\ H,\ j)$ 또는 $(i,\ (j+1)\ {\rm mod}\ W)$ 여야 한다.

모든 칸을 칠하고 칸 $(0,\ 0)$ 에서 과정을 끝내는 방법의 수를 $10^9+7$ 로 나눈 나머지를 구하라. 뱀장어가 지나간 경로가 다르면 서로 다른 방법으로 본다.

입력

$H$ $W$

출력

답을 $10^9+7$ 로 나눈 나머지를 출력한다.

제한

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

힌트

다음 그림은 예제 1의 두 가지 방법을 나타낸다.

예제5

예제 1
입력
```
2 2
```
예상 출력
```
2
```
예제 2
입력
```
6 3
```
예상 출력
```
3
```
예제 3
입력
```
3 4
```
예상 출력
```
0
```
예제 4
입력
```
10 10
```
예상 출력
```
260
```
예제 5
입력
```
200 300
```
예상 출력
```
551887980
```