Nemmo Nemmo (Hard)

Time limit2sMemory limit512 MB

Summary

Count subsets of occupied cells in an N by M grid (N times M at most 300) that contain no full 2 by 2 square, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics, Matrix
Solved: No attempts yet

Problem

Nemo liked falling block puzzle games so much that he built one of his own, Nemmo Nemmo, played on a rectangular grid with a mysterious creature called a nemmo. The rules are short. Pick any empty cell of the grid and put one nemmo on it, or find four occupied cells that form a $2 \times 2$ square and remove every nemmo on them. Repeat one of the two moves until you get bored.

four nemmos forming a 2 x 2 square disappear together

The game turned out to be no fun at all, and Nemo got bored very quickly. Disappointed, he played for a while and decided to quit the moment he wants to remove nemmos but the grid holds no removable nemmo. Count the arrangements of nemmos that can be on the grid when Nemo quits.

Input

The first line contains the number of rows $N$ and the number of columns $M$ of the grid, separated by a space. ( $1 \le N, M \le 300$ , $1 \le N \times M \le 300$ )

Output

Print on the first line the number of arrangements on the given grid in which the occupied cells form no $2 \times 2$ square anywhere, modulo $10^9 + 7$ .

Hint

On a $2 \times 2$ grid, only one of the $2^4 = 16$ arrangements is excluded, the one that fills all four cells, so the answer is 15.

On a $5 \times 7$ grid, 11,185,495,872 arrangements satisfy the condition.

Examples3

Example 1
Input
```
2 2
```
Expected output
```
15
```
Example 2
Input
```
3 5
```
Expected output
```
22077
```
Example 3
Input
```
5 7
```
Expected output
```
185495795
```