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