BrokenTiles plans to expand into the backyards of wealthy clients with patterns of black and white tiles, each measuring 1 x 1 meter. It is known that the yards of all wealthy people have the most fashionable for today shape of a rectangle N x M meters. However, when drawing up a financial plan, the director of this organization had two serious problems: firstly, each new client, obviously, wants the pattern laid out in his yard to be different from the patterns of all other clients of this company, and secondly, this pattern should be cute.
A study has shown that a pattern is pretty if it does not contain a 2 x 2 meter square completely covered with tiles of the same color. To draw up a financial plan, director Vasya needs to find out how many customers he can serve before cute patterns of this size run out. Help him!
Input
Enter two positive integers N and M (1 ≤ N · M ≤ 30).
Imprint
Output a single number – number of different cute patterns that can be laid out in an N x M yard. Patterns that are made from each other by shifting, rotating or reflecting are considered different.
Examples
| # |
Input |
Output |
| 1 |
1 2 |
4 |
| 2 |
2 3 |
50 |