Coloring a Rectangle

Time limit2sMemory limit512 MB

Summary

Count colorings of an N x M grid where every colored cell has an even number of colored side-neighbors.

Level: Medium7 of 10
Topics: Dynamic programming, Bit manipulation, Implementation
Solved: No attempts yet

Problem

A rectangle of size $N \times M$ is divided into unit squares. Write a program that counts the ways to color its cells so that both conditions below hold.

Every cell is either colored or empty.
For each colored cell, the number of colored cells that share a side with it is even.

Empty cells carry no condition. Coloring no cell at all counts as one way.

The picture below is an example with $N = 4$ and $M = 7$ . Yellow cells are colored and black cells are empty.

Given $N$ and $M$ , count the colorings.

Input

The first line contains $N$ and $M$ . ( $1 \le N \le 100$ , $1 \le M \le 8$ )

Output

Print the number of colorings modulo 1,000,000,007 on the first line.

Hint

For $N = 2$ and $M = 2$ the 8 colorings below are possible.

Examples4

Example 1
Input
```
1 1
```
Expected output
```
2
```
Example 2
Input
```
2 2
```
Expected output
```
8
```
Example 3
Input
```
1 3
```
Expected output
```
5
```
Example 4
Input
```
47 7
```
Expected output
```
944149920
```