Matching Colors

Time limit0.4sMemory limit1024 MB

Summary

Count the red and blue fillings of an N by M grid where every cell has a same-colored cell in its row or column, modulo 1000000007.

Level: Hard8 of 10
Topics: Combinatorics, Math
Solved: No attempts yet

Statement

Elly has a grid sheet of paper with $N$ rows and $M$ columns. She wants to fill each cell with red or blue. She insists that every cell of a certain color has at least one other cell of the same color in the same row or the same column, so that it does not feel alone.

Each cell needs a same-colored partner either in its row or in its column. It does not have to be both, although having both is allowed. A row or column may contain more than one matching cell. For example, an entire row filled with red is valid. The sheet does not have to use both colors, so a sheet that is entirely blue can be valid.

Elly wonders how many ways she can fill the sheet. Two fillings are different if some cell is red in one and blue in the other.

Input

The first and only line contains two integers $N$ and $M$ , the number of rows and columns of the paper.

Output

Print one integer: the number of different ways to fill the paper, modulo 1 000 000 007.

Examples4

Example 1
Input
```
3 3
```
Expected output
```
284
```
Example 2
Input
```
5 4
```
Expected output
```
898416
```
Example 3
Input
```
13 17
```
Expected output
```
390317257
```
Example 4
Input
```
42 42
```
Expected output
```
193467102
```