ture

Gigel has a chessboard with N lines and M columns. He wants to place on the chessboard K rooks so that they do not attack each other (taking into consideration that two rooks attack each other if they are on the same line or on the same column). To make things more interesting, Gigel has marked certain squares in which no rook can be placed and now he wants to know in how many ways he can place the rooks.

Line one of input file ture.in contains three positive integers, N, M, and K, each separated by a space. Line two contains P, the number of squares marked by Gigel. Following are P lines of two numbers, x, y, with the meaning that Gigel marked the square on line x and column y.

Output file ture.out will contain a single line with the number of possibilities for placing the rooks on the chessboard.

• 0 <= N*M <= 250
• 0 <= K <= 100
• 0 <= P <= N*M

ture.in	ture.out
3 3 3 1 2 2	4

Time limit: 0.3 seconds/test

Diaconu Adrian Paul
University of Bucharest, Mathematics & IT Department
ditzone@gmail.com