Симпатичные узоры 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. Узоры, полученные друг из друга сдвигом, поворотом или отражением, считаются разными.
Example 1