P4684 [IOI 2008] Fish

According to Scheherazade, there is a lake in a faraway desert. Initially, there are $F$ fish in the lake. Choose the most valuable $K$ types of gems, and for each of the $F$ fish, feed it exactly one gem. Note that since $K$ may be smaller than $F$, two or more fish may swallow the same type of gem. As time goes by, some fish eat other fish. A fish can eat another fish if and only if its length is at least twice the length of the fish being eaten ($A$ can eat $B$ if and only if $L_A \geq 2L_B$). There is no rule saying when a fish will eat another fish. Some fish may eat several smaller fish one after another, and some fish may eat none, even if they are able to. When a fish eats a smaller fish, its length does not change, but the gems inside the smaller fish remain intact and move into the bigger fish’s stomach. According to Scheherazade, if you can find that lake, you will be allowed to catch one fish and take the gems inside its stomach. You want to try your luck, but before setting out, you want to know how many different gem collections you might obtain by catching a fish. Write a program that, given the length of each fish and the type of gem it initially swallowed, finds the number of different gem collections that can appear in a fish’s stomach, modulo a given integer $M$. A collection is defined by the count of each type of gem, and the order of gems does not matter. Any two gems of the same type are indistinguishable.

Your program should read the following data from standard input: - The first line contains an integer $F$, the initial number of fish in the lake. - The second line contains an integer $K$, the number of gem types. Different gem types are represented by integers from $1$ to $K$. - The third line contains an integer $M$. - Each of the next $F$ lines contains two integers separated by a space, describing a fish: its length and the type of gem in its stomach. Note: In all test cases, each of the $K$ gem types appears at least once.

Your program should output to standard output a single integer between $0$ and $M-1$ (inclusive), the number of all possible different gem collections modulo $M$, on one line. Note that in solving the problem, the value $M$ has no purpose other than simplifying computation.

### Constraints There are testdata worth 70 points in total where $K$ does not exceed $7,000$. Among these, there are testdata worth 25 points where $K$ does not exceed $20$. For all testdata, $1 \leq F \leq 500,000$, $1 \leq K \leq F$, $2 \leq M \leq 30,000$, $1 \leq L_X \leq 1,000,000,000$. ### Sample Explanation There are $11$ possible collections, so you should output $4$, which is $11$ modulo $7$. These collections are: $[1] [1,2] [1,2,3] [1,2,3,3] [1,3] [1,3,3] [2] [2,3] [2,3,3] [3]$ and $[3,3]$. (For each collection, we list the gems it contains. For example, $[2,3,3]$ contains one type $2$ gem and two type $3$ gems.) These collections can be obtained in the following ways: $[1]$: If you catch the second fish (or the fourth fish) before it eats any other fish. $[1,2]$: If the second fish eats the first fish, it will have one type $1$ gem (the one it swallowed initially) and one type $2$ gem (obtained from the first fish’s stomach). $[1,2,3]$: One possible way is: the fourth fish eats the first fish, then the third fish eats it. If you catch the third fish at this moment, it has one gem of each of these three types in its stomach. $[1,2,3,3]$: The fourth fish eats the first fish, the third fish eats the fourth fish, the third fish eats the fifth fish, and you catch the third fish. $[1,3]$: The third fish eats the fourth fish, and you catch the third fish. $[1,3,3]$: The third fish eats the fifth fish, the third fish eats the fourth fish, and you catch the third fish. $[2]$: You catch the first fish. $[2,3]$: The third fish eats the first fish, and you catch the third fish. $[2,3,3]$: The third fish eats the first fish, the third fish eats the fifth fish, and you catch the third fish. $[3]$: You catch the third fish. $[3,3]$: The third fish eats the fifth fish, and you catch the third fish. Translated by ChatGPT 5