Black and White

Each cell is black or white with probability 1/2; find the expected product of the number of all-black subrectangles and all-white subrectangles.

Hard8CombinatoricsProbabilityMathDynamic programmingNo attempts yetTime limit2sMemory limit512 MB

Problem

A rectangle is cut into H×WH \times W squares of size 1×11 \times 1, so it has HH rows and WW columns. Each square is painted black or white. Each color has probability 50%, and the squares are independent.

A subrectangle is built by choosing at least one row and at least one column, then keeping only the squares that lie in a chosen row and in a chosen column. The chosen rows do not have to be adjacent, and neither do the chosen columns. For example, in a 3×53 \times 5 rectangle, choosing rows 1 and 3 together with columns 2, 4 and 5 keeps the six squares shown below.

Two subrectangles are different whenever the chosen set of rows differs or the chosen set of columns differs, even if the coloring that remains looks the same. A subrectangle whose squares are all black is a black subrectangle, and one whose squares are all white is a white subrectangle.

Compute the expected value of the number of black subrectangles times the number of white subrectangles.

Input

The first line contains two integers HH and WW, the size of the rectangle, separated by one space. (1H,W1031 \le H, W \le 10^3)

Output

Write the expected value as a reduced fraction a/ba/b and print (a×b1)mod1000000007(a \times b^{-1}) \bmod 1000000007. Here b1b^{-1} is the multiplicative inverse of bb modulo 10000000071000000007. The answer exists for every input that satisfies the constraints.