Cute patterns 2#1866
BrokenTiles plans to create patterns in the yards of wealthy clients using black and white tiles, each measuring 1 \times 1 meter. All yards of these clients are rectangles of size n \times m meters.
However, the company's director faces two major concerns when planning the finances. First, every new client wants the pattern in their yard to be distinct from the patterns in the yards of all previous clients. Second, each pattern must be attractive.
A pattern is attractive if it does not contain anywhere a 2 \times 2 square covered completely with tiles of the same color.
The director needs to know how many clients can be served before all possible attractive patterns of a given size run out. Help him!
The first line contains two positive integers and such that 1 \leq n \cdot m \leq 300.
Print a single integer — the number of distinct attractive patterns that can be created for a yard of size n \times m modulo 2^{30} + 1. Patterns obtained from one another by shifting, rotation, or reflection are considered different.
Example 1