N-Rook II

At most one rook may be placed on each square of a chessboard. A rook can attack another rook in the same row or the same column.

You want to place K rooks on an N × M chessboard. Count the number of placements in which each rook is attacked by at most one other rook. A rook may also be attacked by no other rooks.

The first line contains N, the number of rows of the chessboard.

The second line contains M, the number of columns of the chessboard.

The third line contains K, the number of rooks to place.

Print the number of ways to place K rooks on an N × M chessboard so that each rook is attacked by at most one other rook, modulo 1,000,001.

• 1 ≤ N, M ≤ 100
• 1 ≤ K ≤ 100