Nemmo Nemmo (Easy)

Time limit1sMemory limit512 MB

Summary

Count subsets of cells of an N by M grid, with N*M at most 25, that contain no full 2 by 2 square of chosen cells.

Level: Easy3 of 10
Topics: Brute force, Bit manipulation, Combinatorics, Math
Solved: No attempts yet

Problem

Nemo was deeply impressed by the game Puy×××, so he invented "Nemmo Nemmo", played on a rectangular grid with a mysterious creature called a "Nemmo". The rules are very simple. Pick any empty cell of the grid and put one "Nemmo" on it, or find four cells holding "Nemmo"s that form a $2 \times 2$ square and remove all four at once. Repeat the two moves until you get bored.

The game turned out to be no fun at all, and Nemo got bored very quickly. He decided to play for a while and then stop the moment he wanted to remove some "Nemmo"s but no removable "Nemmo" was left on the grid. Count the arrangements of "Nemmo"s that can appear when Nemo stops.

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 25$ , $1 \le N \times M \le 25$ )

Output

Print on the first line the number of arrangements on the given grid in which no four cells holding "Nemmo"s form a $2 \times 2$ square.

Hint

On a $2 \times 2$ grid, 15 of the $2^4 = 16$ arrangements satisfy the condition. The only excluded one is the arrangement with a "Nemmo" on all four cells.

Examples3

Example 1
Input
```
2 2
```
Expected output
```
15
```
Example 2
Input
```
2 3
```
Expected output
```
57
```
Example 3
Input
```
3 5
```
Expected output
```
22077
```