Дима любит рисунки на клетчатом листке бумаги. А еще больше Дима любит рисунки, которые изображают одну из его любимых фигур.
Клетчатый листок размера n × m представляет собой таблицу, состоящую из n строк и m столбцов. На чистом клетчатом листке — все клетки белые. Рисунком Дима называет изображение на чистом клетчатом листке, полученное закрашиванием некоторых клеток в черный цвет.
Рисунок изображает одну из любимых фигур Димы, если выполняются следующие условия:
- Рисунок содержит хотя бы одну закрашенную клетку;
- Все закрашенные клетки образуют связное множество, то есть из любой закрашенной клетки можно дойти до любой другой (из клетки можно перейти в соседнюю по стороне);
- Минимальное количество перемещений, за которое можно дойти из закрашенной клетки с координатами (x1, y1) в закрашенную клетку с координатами (x2, y2), двигаясь только по закрашенным клеткам, равно |x1 - x2| + |y1 - y2|.
Сейчас Диму интересует вопрос: сколько существует рисунков на листке размера n × m, которые изображают одну из его любимых фигур? Посчитайте это количество по модулю 1000000007 (109 + 7).
Выходные данные
В единственную строку выведите остаток от деления ответа на задачу на число 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
|
13
|
|
2
|
3 4
|
571
|