만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

창문

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

요약
H x W 격자에서 모든 부분 직사각형을 균등 확률로 고를 때, 제거되는 칸 수의 기댓값에 9를 곱한 값을 1e9+7로 나눈 나머지로 구한다.
난이도

보통10점 중 5점

유형
수학, 조합론, 확률, 누적 합
정답자
아직 제출이 없습니다

문제

그가 사는 집의 한 벽면은 1×11 \times 1 크기의 정사각형 벽돌이 세로로 HH행, 가로로 WW열 쌓인 직사각형이다.

창문이 없는 집이 너무 답답해서, 그는 벽돌 몇 개를 제거해 창문을 내려고 한다. 창문을 낼 것이므로 제거하는 벽돌은 빈틈 없이 붙은 하나의 직사각형을 이루어야 한다.

창문을 다는 일은 나중에 생각하기로 하고, 우선 창문이 들어갈 자리를 정해 그 자리의 벽돌을 모두 제거하기로 했다. 그는 무작위를 좋아해서, 창문을 놓을 수 있는 H(H+1)2×W(W+1)2\frac{H(H+1)}{2} \times \frac{W(W+1)}{2}가지 자리 가운데 하나를 균등한 확률로 골라 그 자리의 벽돌을 모두 제거한다. 벽돌 하나를 제거하는 비용은 9원이다.

그가 벽돌을 제거하는 데 드는 비용의 기댓값을 출력하는 프로그램을 작성하라.

입력

첫째 줄에 벽의 크기를 나타내는 두 자연수 HH와 WW가 공백 하나를 사이에 두고 주어진다. (1≤H,W≤10181 \le H, W \le 10^{18})

출력

그가 벽돌을 제거하는 데 드는 비용의 기댓값을 출력한다. 정확한 채점을 위해, 답을 기약분수로 나타내어 ab\frac{a}{b}가 되면 a×b−1a \times b^{-1}을 1,000,000,007로 나눈 나머지를 대신 출력한다. 여기서 b−1b^{-1}은 bb의 모듈러 곱셈 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.

예제4

  1. 예제 1

    입력
    1 1
    
    예상 출력
    9
    
  2. 예제 2

    입력
    3 5
    
    예상 출력
    35
    
  3. 예제 3

    입력
    8 10
    
    예상 출력
    120
    
  4. 예제 4

    입력
    1234567890 999999999999
    
    예상 출력
    259384379