Martian Plates#4955
In a Martian restaurant, there are different dishes. A festive dinner consists of dishes (where l = t/2) served in sequence. Some dishes may appear more than once at the dinner, while others may not appear at all. During the dinner, plates are stacked on top of each other as they are brought to the table. The waiter may either bring a new dish (placing its plate on top) or remove the plate from the top of the stack when it is empty. However, a plate cannot be removed until all plates placed after it have also been removed (that is, plates must be removed in the reverse order they were added).
Additionally, there are certain traditions for some ordered pairs of dishes: for some pairs , the custom is that dish cannot be brought to the table while the plate from dish is still on the table. Such pairs are called "uncommon pairs."
Let us define a schedule of the waiter as the sequence of bringing in dishes and removing empty plates. Thus, the schedule consists of t = 2l actions. Your task is to determine how many distinct valid schedules exist for a festive dinner of dishes, modulo .
The first line of input contains four integers: (2 \leq p \leq 10^4), (1 \leq t \leq 200, is even), (1 \leq n \leq 10), and (1 \leq m \leq 100) — the modulus, the total number of schedule actions (t = 2l), the number of dishes available in the restaurant, and the number of uncommon pairs, respectively.
The next lines each contain two integers and (1 \leq i, j \leq n), indicating that dish cannot be brought to the table while the plate from dish remains on the table.
Output the number of distinct valid schedules, modulo .
Example 1