Tasty Cakes

Time limit1sMemory limit1024 MB

Summary

Count the shadings of an N x M grid whose unshaded cells can be exactly tiled by 1 x 2 dominoes, modulo 1000000007.

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

Statement

Every summer vacation day, Misha drew a neat rectangular field of N × M cells in his notebook and shaded some of the cells. Each day produced a new picture, different from all the others, so Misha made $2^{NM}$ pictures in total (shaded cells are gray in the figure below).

Every day his friend Volodya took one of Misha's pictures and tried to cover the unshaded cells with 1 × 2 rectangles. Every unshaded cell must be covered, a rectangle cannot cover a shaded cell, rectangles cannot extend outside the field, and rectangles cannot overlap.

Volodya did not always succeed (the cases where he succeeded for N = 2 and M = 2 are shown in the figure above). On the few days when he did succeed, Misha's mother was so pleased for the boys that she baked them a cake. How many cakes did she bake?

Input

The first line contains two integers N and M, the field size ( $1 \le N \le 6$ , $1 \le M \le 500$ ).

Output

Print a single number, the number of cakes modulo $10^9 + 7$ .

Examples2

Example 1
Input
```
2 2
```
Expected output
```
6
```
Example 2
Input
```
2 3
```
Expected output
```
18
```