Cute patterns 1#1761
The company BrokenTiles plans to lay a pattern of black and white tiles, each of size 1 \times 1 meter, in the yards of wealthy clients. It is known that all such yards are currently considered fashionable if they are rectangular, measuring n \times m meters.
However, while preparing the financial plan, the director of the company encountered two major problems: first, each new client will obviously want the pattern in their yard to be distinct from the patterns of all other clients of the company; and second, the pattern must be aesthetically pleasing.
A study showed that a pattern is aesthetically pleasing if there is no 2 \times 2 square completely covered with tiles of the same color anywhere in the yard.
To finalize the financial plan, the director needs to know how many clients they can serve before they run out of distinct aesthetically pleasing patterns for a given size. Help him!
The first line contains two positive integers and . 1 \le n \cdot m \le 30.
Output a single integer — the number of different aesthetically pleasing patterns that can be laid out in a yard of size n \times m. Patterns obtained from one another by shifting, rotating, or reflecting are considered different.
Beispiel 1