흑백

각 칸이 검정 또는 흰색일 확률이 1/2일 때, 모든 칸이 검정인 부분직사각형의 수와 모두 흰색인 부분직사각형의 수의 곱의 기댓값을 구한다.

어려움8조합론확률수학동적 계획법아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

1×11 \times 1 크기의 정사각형 칸 H×WH \times W 개로 이루어진 직사각형이 있다. 즉 이 직사각형은 HH 개의 행과 WW 개의 열로 나뉜다. 각 칸은 흑색 또는 백색으로 칠해지며, 두 색이 나올 확률은 각각 50%이고 칸마다 서로 독립이다.

부분 직사각형은 행을 한 개 이상, 열을 한 개 이상 고른 다음 고른 행과 고른 열이 만나는 칸만 남겨서 만든다. 고르는 행끼리 붙어 있을 필요는 없고, 고르는 열끼리도 마찬가지다. 예를 들어 3×53 \times 5 직사각형에서 첫 번째 행과 세 번째 행을 고르고 두 번째 열, 네 번째 열, 다섯 번째 열을 고르면 아래 그림의 여섯 칸이 남는다.

칠해진 모양이 같더라도 고른 행의 집합이나 열의 집합이 다르면 서로 다른 부분 직사각형으로 센다. 한 부분 직사각형에 속한 칸이 모두 흑색이면 흑색 부분 직사각형, 모두 백색이면 백색 부분 직사각형이라고 한다.

흑색 부분 직사각형의 개수와 백색 부분 직사각형의 개수를 곱한 값의 기댓값을 구하라.

입력

첫째 줄에 직사각형의 크기를 나타내는 자연수 HHWW 가 공백 하나를 사이에 두고 주어진다. (1H,W1031 \le H, W \le 10^3)

출력

기댓값을 기약분수 a/ba/b 로 나타냈을 때 (a×b1)mod1000000007(a \times b^{-1}) \bmod 1000000007 을 출력한다. b1b^{-1}10000000071000000007 을 법으로 하는 bb 의 곱셈 역원이다. 제약을 만족하는 모든 입력에 대해 답이 존재한다.