Fish

Time limit3sMemory limit128 MB

Summary

Given fish lengths and gem kinds, count how many distinct gem-count combinations a single fish can ever hold, modulo M, where a fish can eat another only if at least twice as long.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Combinatorics, Tree
Solved: No attempts yet

Problem

Far away, in the middle of a desert, there is a lake. Originally the lake held $F$ fish. Among the most valuable gemstones on Earth, $K$ different kinds were chosen, and each of the $F$ fish was made to swallow exactly one gem. Because $K$ may be smaller than $F$ , several fish may have swallowed gems of the same kind.

As time went by, some fish ate others. One fish can eat another if and only if it is at least twice as long: fish $A$ can eat fish $B$ exactly when $L_A \ge 2 \cdot L_B$ . There is no rule about when a fish decides to eat — a fish may eat several smaller fish one after another, or choose to eat none at all even when it could. When a fish eats a smaller one its own length does not change, and every gem in the smaller fish's stomach passes, undamaged, into the larger fish's stomach.

You are allowed to take a single fish out of the lake and keep all the gems currently in its stomach. Before setting out, you want to know how many different gem combinations you could obtain by catching one fish.

Write a program that, given the length of each fish and the kind of gem it originally swallowed, computes the number of different gem combinations that can end up in the stomach of some fish, modulo a given integer $M$ . A combination is determined solely by how many gems of each of the $K$ kinds it contains: gems have no order, and two gems of the same kind are indistinguishable.

Input

The first line contains the integer $F$ , the original number of fish in the lake ( $1 \le F \le 500{,}000$ ).
The second line contains the integer $K$ , the number of gem kinds. Kinds are numbered $1$ through $K$ ( $1 \le K \le F$ ).
The third line contains the integer $M$ ( $2 \le M \le 30{,}000$ ).
Each of the next $F$ lines describes one fish with two space-separated integers: the fish's length followed by the kind of gem it originally swallowed ( $1 \le L_X \le 1{,}000{,}000{,}000$ ).

It is guaranteed that at least one gem of each of the $K$ kinds is present.

Output

Print a single line containing one integer between $0$ and $M-1$ inclusive: the number of different possible gem combinations, taken modulo $M$ . The value of $M$ has no meaning beyond keeping the numbers small.

Examples3

Example 1
Input
```
5
3
7
2 2
5 1
8 3
4 1
2 3
```
Expected output
```
4
```
Example 2
Input
```
1
1
2
5 1
```
Expected output
```
1
```
Example 3
Input
```
3
1
1000
1 1
2 1
4 1
```
Expected output
```
3
```