...И с вами снова... Теле-Майк!
Устали от однообразного интерьера? Надоела серая обыденность? Мечтаете о головокружительных изменениях вашей скромной обители? У нас есть, что предложить вам!
Этот Ковёр-из-домино всего за $99.99 изменит вашу жизнь! Вы можете постелить им пол, повесить его на стену или даже на потолок! Кроме всего прочего...
Вирус Хексадесимал, насмотревшись рекламы, захотела заполучить такой Ковёр-из-домино и обязательно сфотографироваться на его фоне. Но ясное дело — вирус никогда не согласится покупать лицензионный Ковёр! Поэтому она заказала грузовик домино и решила смастерить такой Ковёр сама.
Оригинальный Ковёр-из-домино представляет собой поле из квадратиков размера n × m. Каждый квадратик является половиной кости домино и может быть ориентирован либо вертикально, либо горизонтально, независимо от соседей. Вертикально ориентированные половинки домино выглядят так:
А горизонтально ориентированные вот так:
Отсюда можно заметить, что некоторые половинки выглядят одинаково в обоих положениях, а некоторые — по-разному.
Кости домино, которые купила Хексадесимал, представляют собой неразрезаемые фишки размера 1 × 2, которые можно класть либо вертикально, либо горизонтально. Если кость расположить вертикально, то обе её половинки должны быть вертикально ориентированными; если горизонтально, то обе половинки должны быть ориентированы горизонтально.
Ниже приведены правильные и неправильные примеры вертикально и горизонтально расположенных костей домино:
Вирус Хексадесимал собирает свой собственный Ковёр-из-домино так, что выполняются следующие условия:
- каждая клетка ковра покрыта костью домино, т.е. нет пустых клеток;
- все кости домино лежат строго внутри ковра и не накладываются друг на друга;
- если есть горизонтальная кость домино, у которой левая половина лежит в столбце j, то нет горизонтальных костей домино, у которых левая половина лежит в столбце j - 1 или j + 1.
Прежде чем начать собирать свой собственный Ковёр-из-домино, вирус хочет узнать количество способов достичь намеченной цели по модулю 109 + 7.
Можете предполагать, что количество костей домино каждого вида у вируса бесконечно велико.