Electricity

The residents of Bytelon decided to power their homes with wind energy, so they built a row of windmills.

Only one road runs through Bytelon. Every home stands in a straight line on one side of that road, and the windmills stand in a straight line on the opposite side. Some windmills are joined to some homes by high-voltage lines that run across the road. A single windmill may be joined to several homes, a single home may be joined to several windmills, and some windmills or homes may be joined to nothing at all. Every line is a straight segment, and for any (home, windmill) pair there is at most one line.

The government prefers a tidier arrangement. It wants to keep only some of the existing lines so that both of the following hold.

• Each windmill feeds at most one home, and each home is fed by at most one windmill.
• Viewed from above, no two kept lines cross. (Because the homes and the windmills each lie on parallel lines, every kept line looks straight; two kept lines must not intersect, otherwise the wind could push them together and cause a short circuit.)

Count how many subsets of the existing lines satisfy both conditions. The empty subset, which keeps no line at all, counts as one valid arrangement.

Because the count can be enormous, output it modulo a number $r$ chosen by the government.

Write a program that reads the existing lines from standard input and writes to standard output the number of valid subsets modulo $r$.

The first line contains four integers $n$, $m$, $k$, and $r$ separated by single spaces.

• $1 \le n, m \le 200\,000$: the number of homes and the number of windmills. Homes are numbered $1$ to $n$ in the order they appear along the road, and windmills are numbered $1$ to $m$ in the same direction on the opposite side.
• $1 \le k \le 1\,000\,000$: the number of existing high-voltage lines.
• $2 \le r \le 10^9$: the divisor chosen by the government.

Each of the next $k$ lines contains two integers $h_i$ and $w_i$ ($1 \le h_i \le n$, $1 \le w_i \le m$), meaning the $i$-th line joins home $h_i$ with windmill $w_i$. No (home, windmill) pair appears more than once.

Print a single integer on one line: the number of valid subsets of the existing lines, taken modulo $r$.

For the configuration in the picture there is exactly $1$ way to keep no line, $5$ ways to keep a single line, $2$ ways to keep two lines, and no way to keep three lines, for a total of $8$.

Two kept lines cross exactly when one starts at a lower-numbered home yet ends at a higher-numbered windmill than the other. So a valid subset is a set of lines whose home indices and windmill indices increase together.