Yet Another Rooks Problem

You have k rooks and an m×n board. The placement of rooks on the board is called correct if no rook is between two other rooks, horizontally or vertically.

Given m, n and k find the number of correct placements of rooks on the board. Since this number may be quite large, find it modulo 10003.

Input

Input file contains m, n and k (1 ≤ m, n ≤ 50, 1 ≤ k ≤ m∙n).

Output

Output one number - the number of correct placements of k rooks on the m×n board modulo 10003.

Examples