Fish#276

Fish

9 seconds

64 megabytes

Hard

It was told by Scheherazade that far away, in the middle of the desert, there is a lake. Originally, this lake had $F$ fish in it. $K$ different kinds of gemstones, chosen among the most valuable on Earth, were selected, and each of the $F$ fish swallowed exactly one gem. Since $K$ might be less than $F$ , two or more fish might swallow gems of the same kind.

As time went by, some fish ate some of the other fish. One fish can eat another if and only if it is at least twice as long (fish $A$ can eat fish $B$ if and only if $L_{A} \geq 2 L_{B}$ L_A \geq 2L_B). There is no rule that determines when or whether a fish decides to eat another. A fish may decide to eat several smaller fish, while some fish may decide not to eat any, even if they could. When a fish eats a smaller fish, its length does not change, but all the gems from the smaller fish's stomach end up undamaged in the larger fish's stomach.

Scheherazade said that if you find the lake, you are allowed to take exactly one fish and keep all the gems in its stomach. Of course, you would like to try your luck, but before setting out, you wish to know how many different combinations of gems you could possibly obtain by catching a single fish.

Given the length of each fish, and the kind of gemstone originally swallowed by each fish, write a program that finds the number of different combinations of gems that may end up in the stomach of any fish, modulo a given integer $M$ . A combination is defined only by the number of gems of each of the $K$ kinds. There is no concept of order among the gems, and any two gems of the same kind are indistinguishable.

$1 \leq F \leq 500000$ 1 \leq F \leq 500\,000

$1 \leq K \leq F$ 1 \leq K \leq F

$2 \leq M \leq 30000$ 2 \leq M \leq 30\,000

$1 \leq L_{X} \leq 1000000000$ 1 \leq L_X \leq 1\,000\,000\,000

where $F$ is the initial number of fish in the lake, $K$ is the number of different gemstone kinds, $M$ is the modulus, and $L_{X}$ L_X is the length of fish $X$ .

Input

Your program must read from the standard input the following data:

Line $1$ contains the integer $F$ : the original number of fish in the lake.
Line $2$ contains the integer $K$ : the number of kinds of gemstones. The kinds of gemstones are represented by integers from $1$ to $K$ inclusive.
Line $3$ contains the integer $M$ .
Each of the next $F$ lines describes one fish, using two integers separated by a space: the length of the fish and the kind of gemstone originally swallowed by that fish.

Note: For all test cases used for evaluation, it is guaranteed that there is at least one gemstone of each of the $K$ kinds.

Output

Your program must write to the standard output a single line containing a single integer between $0$ and $M - 1$ M-1 (inclusive): the number of different possible combinations of gemstones modulo $M$ .

Note: The value $M$ has no importance other than simplifying computations.

Examples

Example 1