Mosaic

An architect wants to decorate a building with a long, thin mosaic. The mosaic occupies a rectangular strip that is $N$ inches tall and $M$ inches wide. Think of the strip as an $N \times M$ grid of unit cells, where each cell is one inch by one inch.

He has two kinds of tiles, and each tile fits inside a $2 \times 2$ block of cells:

• A square tile that covers all four cells of a $2 \times 2$ block.
• An L-shaped tile (an L-tromino) that covers exactly three cells of a $2 \times 2$ block, leaving one corner cell empty. This tile may be rotated into any of its four orientations.

He wants to cover the whole strip so that every cell is covered exactly once, with no gaps and no overlapping tiles. He wonders how many different patterns he can make.

Two mosaics are considered the same only when they use the same kinds of tiles in exactly the same positions. If a rotation or reflection of a pattern places tiles in different cells, it counts as a different pattern. For example, the four $4 \times 16$ mosaics below are rotations or reflections of one another, yet the architect counts them as four different mosaics:

The input contains several test cases. Each test case is a single line with two integers $N$ and $M$ ($2 \le N \le 10$, $2 \le M \le 500$): the height and the width of the strip, in inches. The input ends with a line containing two zeros; this terminating line is not a test case.

For each test case, print one line containing a single integer: the number of distinct tilings of the $N \times M$ strip, taken modulo $10^6 = 1{,}000{,}000$. Print no extra whitespace, and print no blank lines between answers.