Симпатичні візерунки 2#1866
BrokenTiles планує створювати візерунки на подвір'ях заможних клієнтів, використовуючи чорні та білі плитки розміром 1 \times 1 метр. Усі подвір'я цих клієнтів є прямокутниками розміром n \times m метрів.
Однак директор компанії стикається з двома основними проблемами при плануванні фінансів. По-перше, кожен новий клієнт хоче, щоб візерунок на його подвір'ї відрізнявся від візерунків у дворах усіх попередніх клієнтів. По-друге, кожен візерунок повинен бути привабливим.
Візерунок є привабливим, якщо ніде в ньому не зустрічається повністю заповнений плитками одного кольору квадрат розміром 2 \times 2.
Директору потрібно знати, скільки клієнтів можна обслужити, перш ніж закінчаться всі можливі привабливі візерунки заданого розміру. Допоможіть йому!
У першому рядку задано два додатних цілих числа та . 1 \leq n \cdot m \leq 300.
Виведіть одне ціле число — кількість різних привабливих візерунків, які можна скласти для подвір'я розміром n \times m за модулем 2^{30} + 1. Візерунки, отримані один з одного зсувом, поворотом або віддзеркаленням, вважаються різними.
Приклад 1