Дима любит рисунки на клетчатом листке бумаги. А еще больше Дима любит рисунки, которые изображают одну из его любимых фигур.

Клетчатый листок размера n × m представляет собой таблицу, состоящую из n строк и m столбцов. На чистом клетчатом листке — все клетки белые. Рисунком Дима называет изображение на чистом клетчатом листке, полученное закрашиванием некоторых клеток в черный цвет.

Рисунок изображает одну из любимых фигур Димы, если выполняются следующие условия:

• Рисунок содержит хотя бы одну закрашенную клетку;
• Все закрашенные клетки образуют связное множество, то есть из любой закрашенной клетки можно дойти до любой другой (из клетки можно перейти в соседнюю по стороне);
• Минимальное количество перемещений, за которое можно дойти из закрашенной клетки с координатами (x₁, y₁) в закрашенную клетку с координатами (x₂, y₂), двигаясь только по закрашенным клеткам, равно |x₁ - x₂| + |y₁ - y₂|.

Сейчас Диму интересует вопрос: сколько существует рисунков на листке размера n × m, которые изображают одну из его любимых фигур? Посчитайте это количество по модулю 1000000007 (10⁹ + 7).