ture

Гигел има шахматна дъска с N реда и M стълба. Той иска да разположи на дъската K топа, по такъв начин, че да не се атакуват един друг (два топа се атакуват взаимно, ако са разположени на един и същи ред или на един и същи стълб. За да станат нещата по-интересни, Гигел е отбелязал някои квадратчета, на които е забранено да се поставя фигура. Сега Гигел иска да знае по колко различни начина могат да се поставят топовете на дъската.

Задача
Помогнете на Гигел да намери броя на различните възможности за разполагане на
K топа.

Вход
Първия ред на входния файл
ture.in съдържа три положителни цели числа N, M и K, разделени с интервал. Втория ред съдържа числото P, броя на квадратчетата, отбелязани от Гигал. Следват P реда, всеки с по две числа x, y, означаващи, че Гигал е отбелязал квадратчето, намиращо се на ред x и стълб y.

Изход
Изходния файл
ture.out трябва да съдържа един ред, на който е записан броя на възможните разполагания на топовете на дъската.

Ограничения

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

Пример

ture.in

ture.out

3 3 3
1
2 2

4

Ограничение за време: 0.3 секунди на тест

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

 (превод на български: Стоян Капралов)