창문 Batch Compilation commands

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

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

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

입력

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

부분문제

부분문제	점수	H, W
1	3	1 ≤ H, W ≤ 50
2	97	1 ≤ H, W ≤ 1018

출력

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

입출력 예제

예제 1

입력

1 1

출력

9

예제 2

입력

3 5

출력

35

예제 3

입력

8 10

출력

120

예제 4

입력

1234567890 999999999999

출력

259384379