В марсианском ресторане всего \textbf{n} блюд, а праздничный обед состоит из \textbf{l} блюд. При этом некоторые блюда во время обеда могут повторяться, а некоторые - не встречаться ни разу. Тарелки во время обеда ставятся прямо друг на друга. Официант при необходимости выносит новые блюда, либо убирает тарелки со стола. При этом ту тарелку, которую официант поставил раньше, он не может унести раньше - на ней стоят другие тарелки. Для некоторых пар блюд на Марсе есть обычай - пока тарелка из-под одного блюда стоит на столе, другое блюдо выносить нельзя (такие пары называют необычными). Расписанием официанта называется порядок, в котором он выносит и убирает тарелки (всего в расписании \textbf{t = 2l} пунктов). Ваша задача - посчитать, сколько всего различных расписаний существует на Марсе, по модулю \textbf{p}. \InputFile В первой строке входного файла находится число \textbf{p} (\textbf{2} ≤ \textbf{p} ≤ \textbf{10^4}) - модуль, \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{200}, \textbf{t} четно) - количество пунктов в расписании, \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10}) - количество блюд в ресторане и \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{100}) - количество необычных пар. В последующих \textbf{m} строках указаны номера блюд \textbf{i} и \textbf{j} - это значит, что блюдо \textbf{j} нельзя выносить, пока на столе тарелка из-под блюда \textbf{i}. \OutputFile В выходной файл выведите количество расписаний по модулю \textbf{p}.