Cute patterns 2
The company plans to do BrokenTiles putting some in the yards of affluent clients a pattern of black and white tiles, each of which has a size of 1×1 meter. It is known that the courts of all wealthy people have the most fashionable today rectangular n×m meters.
However, in drawing up a financial plan from the Director of this organization appeared but two serious problems: first, every new client obviously wants to pattern, laid out in his yard, differed from the patterns of all other customers of this company, and secondly, this pattern should be cute.
The study showed that the pattern is nice, if it found no square 2×2 meters, completely covered with tiles of one color.
The financial plan for the director to find out how many customers they can serve before the cute designs of this size will end. Help him!
Input
On the first line of the input file are two positive integers n and m. 1 ≤ n·m ≤ 300.
Output
Derive the output file a single number - the number of different cute patterns that can be laid out in the yard of size n×m modulo 2^30 + 1. Patterns obtained from one another shift, rotation or reflection are different.