You have \textbf{k} rooks and an \textbf{m}×\textbf{n} board. The placement of rooks on the board is called \textit{correct} if no rook is between two other rooks, horizontally or vertically. Given \textbf{m}, \textbf{n} and \textbf{k} find the number of correct placements of rooks on the board. Since this number may be quite large, find it modulo \textbf{10003}. \InputFile Input file contains \textbf{m}, \textbf{n} and \textbf{k} (\textbf{1} ≤ \textbf{m}, \textbf{n} ≤ \textbf{50}, \textbf{1} ≤ \textbf{k} ≤ \textbf{m∙n}). \OutputFile Output one number - the number of correct placements of \textbf{k} rooks on the \textbf{m}×\textbf{n} board modulo \textbf{10003}.