ENG  RUS Timus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

## 1526. Martian Plates

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
In a martian restaurant, there is a choice of n dishes, and a holiday dinner consists of l dishes. Some of the dishes could appear more than once at the holiday dinner, while some other ones could never appear. During the dinner, plates are placed one above another. The waiter sometimes brings next dishes or takes the empty plates away. However, an empty plate could not be taken away until all the plates from the next delivered dishes are also taken away. Moreover, for some ordered pairs of dishes there is a Martian custom: first of these dishes can not be brought while the plate from the second dish stands on the table; such pairs are called uncommon.
Let's call a time-table of the waiter the order of bringing dishes and taking away plates. Thus, there are 2l items in a time-table. Your task will be to count how many different time-tables exist for a holiday dinner of l dishes modulo p.

### Исходные данные

The first line of input contains p (2 ≤ p ≤ 104), t (1 ≤ t ≤ 200) which is the number of items in a time table, n (1 ≤ n ≤ 10) which is the number of dishes at the restaurant and m (0 ≤ m ≤ 100) — the number of uncommon pairs. The next m lines each contain an ordered pair of numbers i and j which means that the dish j could not be brought while the plate from the dish i stands on the table. Note that the number t is even.

### Результат

Output the number of different time-tables modulo p.

### Примеры

исходные данныерезультат
```10000 4 2 1
1 2
```
```7
```
```9999 6 10 2
2 3
6 7
```
```4866
```
Автор задачи: Dmitry Gozman
Источник задачи: Dmitry Gozman Contest 1, Petrozavodsk training camp, January 2007