406419: GYM102399 C Иванушка-дурачок и теория вероятностей

C. Иванушка-дурачок и теория вероятностейограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Недавно Иванушка-дурачок захотел стать умнее и поэтому начал изучать теорию вероятностей. Он считает, что уже достаточно хорошо понимает данную тему, и стал этим хвастаться перед всеми.

Чтобы не быть голословным, Иванушка пообещал продемонстрировать окружающим свои навыки при помощи случайного рисунка. Рисунок представляет собой клетчатое поле с $$$n$$$ строками и $$$m$$$ столбцами, каждая клетка которого покрашена в белый или чёрный цвет. Иванушка считает, что рисунок случайный, если для любой клетки верно, что среди ее соседей по стороне не более одной клетки такого же цвета, что и она.

Его братья быстро выяснили, что задумал Иванушка. Они долго пытались объяснить ему, что он, дурачок, все ещё плохо понимает, что такое случайность. Но Иванушка так и не поверил им, поэтому они попросили помощи у вас. Они хотят найти количество различных случайных по мнению Иванушки рисунков. Два рисунка называются различными если существует клетка, которая покрашена в разные цвета на этих рисунках. Так как это число может быть слишком большим, найдите остаток от деления его на $$$10^9 + 7$$$.

Входные данные

В единственной строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 100\,000$$$) — количество строк и столбцов клетчатого поля, соответственно.

Выходные данные

Выведите одно целое число — остаток от деления числа случайных рисунков на $$$10^9 + 7$$$.

ПримерВходные данные

2 3

Выходные данные

8

Примечание

На картинке ниже изображены все возможные случайные раскраски поля $$$2$$$ на $$$3$$$.