C. Игра с прямоугольниками
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

В этой задаче Аня и Маша играют в игру. Изначально у них есть клетчатый лист бумаги, на котором нарисован прямоугольник n × m (только рамка, без внутренности). Аня и Маша делают ходы по очереди, первой ходит Аня. На каждом ходу надо внутри предыдущего прямоугольника нарисовать по линиям сетки прямоугольник, который не будет иметь с ним общих точек. Обратите внимание, что, опять же, рисуется только рамка, без внутренности.

В этой игре никто не выигрывает — Аня и Маша просто играют, пока не сделают в сумме k ходов. Посчитайте, сколько в этой игре вариантов развития событий.

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

В первой и единственной строке заданы три целых числа: n, m, k (1 ≤ n, m, k ≤ 1000).

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

Выведите единственное число — количество вариантов развития событий в этой игре. Поскольку это число может быть очень большим, выведите его значение по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3 3 1
Выходные данные
1
Входные данные
4 4 1
Выходные данные
9
Входные данные
6 7 2
Выходные данные
75
Примечание

Два варианта развития событий считаются различными, если получившиеся в итоге картинки различны, то есть в одном варианте нарисован прямоугольник, который не нарисован в другом варианте.

В первом примере у Ани, которая делает первый и единственный ход, есть единственный вариант хода — вставить квадратик 1 × 1 в данный квадрат 3 × 3.

Во втором примере у Ани есть целых 9 вариантов: 4 способа нарисовать квадратик 1 × 1, 2 способа поставить прямоугольник 1 × 2 вертикально, еще 2 — поставить его горизонтально, и еще один способ нарисовать квадратик 2 × 2.