Codeforces Round 594 (Div. 1) |
---|
Закончено |
Недавно Иванушка-дурачок захотел стать умнее и поэтому начал изучать теорию вероятностей. Он считает, что уже достаточно хорошо понимает данную тему, и стал этим хвастаться перед всеми.
В качестве примера, Иванушка продемонстрировал окружающим концепцию случайного рисунка. Рисунок представляет собой клетчатое поле из $$$n$$$ строкам и $$$m$$$ столбцов, каждая клетка которого покрашена в белый или чёрный цвет. Иванушка считает, что рисунок случайный, если для любой клетки верно, что среди её соседей по стороне есть не более одной клетки такого же цвета, что и она.
Его братья быстро выяснили, что задумал Иванушка. Они долго пытались объяснить ему, что он, дурачок, все ещё плохо понимает, что такое случайность. Но Иванушка так и не поверил им, поэтому они попросили помощи у вас. Они хотят найти количество различных случайных (по мнению Иванушки) рисунков. Два рисунка называются различными, если существует клетка, которая покрашена в разные цвета на этих рисунках. Так как число таких картинок может быть достаточно большим, выведите его по модулю $$$10^9 + 7$$$.
Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 100\,000$$$) — количество строк и столбцов клетчатого поля.
Выведите одно целое число — остаток от деления числа случайных рисунков на $$$10^9 + 7$$$.
2 3
8
На картинке ниже изображены все возможные случайные раскраски поля $$$2$$$ на $$$3$$$.
Название |
---|