G. Короли
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Есть шахматная доска размера n × m и k королей. Король бьет все соседние по вертикали, горизонтали и диагонали клетки. Назовем расстановку фигур на доске правильной, если никакие два короля не бьют друг друга. Ваша задача – посчитать количество правильных расстановок k королей по модулю 109 + 9.

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

Единственная строка входных данных содержит три целых положительных числа n, m, k (1  ≤  n, m  ≤  70,  1  ≤  k  ≤  n·m  ≤  70).

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

Выведите единственное число – количество правильных расстановок по модулю 109 + 9.

Пример
Входные данные
2 2 1
Выходные данные
4