В этой задаче Аня и Маша играют в игру. Изначально у них есть клетчатый лист бумаги, на котором нарисован прямоугольник n × m (только рамка, без внутренности). Аня и Маша делают ходы по очереди, первой ходит Аня. На каждом ходу надо внутри предыдущего прямоугольника нарисовать по линиям сетки прямоугольник, который не будет иметь с ним общих точек. Обратите внимание, что, опять же, рисуется только рамка, без внутренности.
В этой игре никто не выигрывает — Аня и Маша просто играют, пока не сделают в сумме k ходов. Посчитайте, сколько в этой игре вариантов развития событий.
Выходные данные
Выведите единственное число — количество вариантов развития событий в этой игре. Поскольку это число может быть очень большим, выведите его значение по модулю 1000000007 (109 + 7).
Примечание
Два варианта развития событий считаются различными, если получившиеся в итоге картинки различны, то есть в одном варианте нарисован прямоугольник, который не нарисован в другом варианте.
В первом примере у Ани, которая делает первый и единственный ход, есть единственный вариант хода — вставить квадратик 1 × 1 в данный квадрат 3 × 3.
Во втором примере у Ани есть целых 9 вариантов: 4 способа нарисовать квадратик 1 × 1, 2 способа поставить прямоугольник 1 × 2 вертикально, еще 2 — поставить его горизонтально, и еще один способ нарисовать квадратик 2 × 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
|
1
|
|
2
|
4 4 1
|
9
|
|
3
|
6 7 2
|
75
|