У вас є k тур та дошка m×n. Розміщення тури на дошці називається правильним, якщо тура не знаходиться між двома іншими турами горизонтально чи вертикально.
Для заданих m, n та k знайдіть кількість правильних розміщень тур на дошці. Так як це число може бути достатньо великим, знайдіть його по модулю 10003.
Вхідні дані містять m, n і k (1 ≤ m, n ≤ 50, 1 ≤ k ≤ m∙n).
Вивести одне число - кількість правильних розміщень k тур на дошці m×n по модулю 10003.