창문
시간 제한1초메모리 제한512 MB
H x W 격자에서 모든 부분 직사각형을 균등 확률로 고를 때, 제거되는 칸 수의 기댓값에 9를 곱한 값을 1e9+7로 나눈 나머지로 구한다.
문제
그가 사는 집의 한 벽면은 크기의 정사각형 벽돌이 세로로 행, 가로로 열 쌓인 직사각형이다.
창문이 없는 집이 너무 답답해서, 그는 벽돌 몇 개를 제거해 창문을 내려고 한다. 창문을 낼 것이므로 제거하는 벽돌은 빈틈 없이 붙은 하나의 직사각형을 이루어야 한다.
창문을 다는 일은 나중에 생각하기로 하고, 우선 창문이 들어갈 자리를 정해 그 자리의 벽돌을 모두 제거하기로 했다. 그는 무작위를 좋아해서, 창문을 놓을 수 있는 가지 자리 가운데 하나를 균등한 확률로 골라 그 자리의 벽돌을 모두 제거한다. 벽돌 하나를 제거하는 비용은 9원이다.
그가 벽돌을 제거하는 데 드는 비용의 기댓값을 출력하는 프로그램을 작성하라.
입력
첫째 줄에 벽의 크기를 나타내는 두 자연수 와 가 공백 하나를 사이에 두고 주어진다. ()
출력
그가 벽돌을 제거하는 데 드는 비용의 기댓값을 출력한다. 정확한 채점을 위해, 답을 기약분수로 나타내어 가 되면 을 1,000,000,007로 나눈 나머지를 대신 출력한다. 여기서 은 의 모듈러 곱셈 역원이다. 이 문제에서는 가능한 모든 입력에 대해 답이 존재한다.