Under construction

Still being built. Things may change

Black and White

Time limit2sMemory limit512 MB

Summary
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.
Level

Hard8 of 10

Topics
Combinatorics, Probability, Math, Dynamic programming
Solved
No attempts yet

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. (1≤H,W≤1031 \le H, W \le 10^3)

Output

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

Examples4

  1. Example 1

    Input
    1 1
    
    Expected output
    0
    
  2. Example 2

    Input
    1 2
    
    Expected output
    500000004
    
  3. Example 3

    Input
    2 2
    
    Expected output
    250000007
    
  4. Example 4

    Input
    99 101
    
    Expected output
    395910821