Симпатичні візерунки 2
Компанія BrokenTiles планує занйятись викладування у подвір'ях заможних клієнтів візерунок з чорних і білих плиток, кожна з яких має розмір 1×1 метр. Відомо, що подвір'я всіх заможних людей мають найбільше модну на сьогодні форму прямокутника n×m метрів.
Проте при складанні фінансового плану у директора цієї організації з'явилось цілих дві серйезних проблеми: по-перше, кожен новий клієнт очевидно захоче, щоб візерунок, викладений у нього на подвір'ї, відрізнявся від візерунків усіх інших клієнтів цієї фірми, і по-друге, цей візерунок повинен бути симпатичним.
Як показали дослідження, візерунок є симпатичним, якщо у ньому ніде не зустрічається квадрат 2×2 метри, повністю покритий плитками одного кольору.
Для складання фінансового плану директору необхідно взнати, скільки клієнтів він зможе обслужити, перед тим як симпатичні візерунки даного розміра закінчаться. Допоможіть йому!
Вхідні дані
У першому рядку вхідного файлу знаходяться два натуральних числа n і m. 1 ≤ n·m ≤ 300.
Вихідні дані
Виведіть у вихідний файл єдине число — кількість різних симпатичних візерунків, які можна викласти на подвір'ї розміром n×m по модулю 2^30 + 1. Візерунки, які отримуються один з одного здвигом, поворотом або віддзеркаленням вважаються різними.