Задача №113166. Марсианские тарелки
В марсианском ресторане могут готовить \(n\) блюд, а воскресный обед состоит из \(l\) блюд. Некоторые из них могут появиться на воскресном обеде более одного раза, некоторые могут вообще не появиться. Во время обеда тарелки складываются одна на другую. Офицант ровно \(2l\) раз заходит в зал и либо приносит очередное блюдо (после того, как съедено блюдо с верхней тарелки), либо забирает пустую верхнюю тарелку. Тем не менее для некоторых упорядоченных пар блюд существует марсианский обычай: первые из блюд не могут появиться в зале пока на столе стоят тарелки от вторых. Такие пары называются несовместимыми.
Назовем расписанием для офицанта порядок, в котором он приносит и уносит тарелки. Таким образом, мы имеем \(2l = t\) событий в расписании. Вы должны вычислить количество различных расписаний для воскресного обеда из \(l\) блюд по модулю \(p\).
Формат входных данных
Первая строка входного файла содержит \(p\) (\(2 \le p \le 10^4\)), \(t\) (\(1 \le t \leq 200\)) — количество событий в расписании, \(n\) (\(1\le n \le 10\)) — количество блюд в ресторане и \(m\) (\(1 \le m \le 100\)) — количество несовместимых пар. Каждая из следующих \(m\) строк содержит упорядоченную пару чисел \(i\) и \(j\), которые означают, что тарелка \(j\) не может быть принесена пока на столе стоит тарелка с номером \(i\). Данное во входном файле число \(t\) четно.
Формат выходных данных
Выведите одно число — количество различных расписаний по модулю \(p\).10000 4 2 1 1 2
7
9999 6 10 2 2 3 6 7
4866