시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 19 15 15 78.947%

문제

그가 사는 집의 한 벽면은 1 × 1크기의 정사각형 벽돌 H × W개로 이루어진 직사각형 형태이다. 즉, 이 벽은 1 × 1 크기의 정사각형 벽돌이 세로로 H행, 가로로 W열 쌓여 있는 것이다.

그는 창문이 없는 집이 너무 답답했기 때문에, 벽에 있는 몇 개의 벽돌을 제거하여 창문을 만들려고 한다. 창문을 만들 것이기 때문에, 제거하는 벽돌들은 하나로 붙어 있는 직사각형 모양을 이루어야 한다.

일단 그는 창문을 설치하는 것은 다음에 생각하도록 하고, 우선 창문을 만들 위치를 정해 그 위치에 있는 모든 벽돌을 제거하기로 했다. 그는 무작위성을 좋아하기 때문에, 설치하는 것이 가능한 창문의 위치 H(H+1)/2 × W(W+1)/2개 중 하나를 무작위로 선택하여 해당하는 모든 벽돌을 제거하려고 한다. 벽돌 하나를 제거하는 데 드는 비용은 9(九)원이다. 그가 벽돌을 제거하기 위해 드는 비용의 기댓값을 출력하는 프로그램을 작성하라.

입력

첫 번째 줄에는 벽의 크기를 나타내는 두 자연수 H 와 W 가 공백 하나로 구분되어 주어진다. (1 ≤ H, W ≤ 1018)

출력

그가 벽돌을 제거하기 위해 드는 비용의 기댓값을 출력한다. 정확한 판별을 위해, 답을 기약분수로 나타내었을 때 a/b가 된다면, (a × b-1) mod 1,000,000,007을 대신 출력하도록 한다. b-1은 b의 모듈러 곱셈에 대한 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

예제 입력

1 1

예제 출력

9

예제 입력 2

3 5

예제 출력 2

35

예제 입력 3

8 10

예제 출력 3

120

예제 입력 4

1234567890 999999999999

예제 출력 4

259384379

힌트

출처

Contest > kriiicon > 제 4회 kriiicon 10번