eolymp
bolt
Try our new interface for solving problems
Problems

Yet Another Rooks Problem

Yet Another Rooks Problem

Time limit 1 second
Memory limit 64 MiB

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 data

Input file contains m, n and k (1m, n50, 1km∙n).

Output data

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

Examples

Input example #1
3 2 3
Output example #1
18