У вас есть \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}). \OutputFile Вывести одно число - количество правильных размещений \textbf{k} ладей на доске \textbf{m}×\textbf{n} по модулю \textbf{10003}.