Ще одна задача про тури

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

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

Вхідні дані

Вхідні дані містять m, n і k (1 ≤ m, n ≤ 50, 1 ≤ k ≤ m∙n).

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

Приклади