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