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