Еще одна задача о ладьях

У вас есть k ладей и доска m×n. Размещение ладьи на доске называется правильным, если ладья не находится между двумя другими ладьями горизонтально или вертикально.

Для заданных m, n и k найдите количество правильных размещений ладей на доске. Так как это число может быть достаточно большим, найдите его по модулю 10003.

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

Входные данные содержат m, n и k (1 ≤ m, n ≤ 50, 1 ≤ k ≤ m∙n).

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

Вывести одно число - количество правильных размещений k ладей на доске m×n по модулю 10003.

Примеры