Gemstone Combinations in the Desert Lake

In a far-off desert, there is a mysterious lake. Initially there are \(F\) fish in the lake. Each fish is fed exactly one gemstone, chosen from the \(K\) most valuable types. Note that since \(K\) can be smaller than \(F\), several fish may receive the same type of gemstone.

Over time, some fish may eat others. A fish \(A\) can eat another fish \(B\) if and only if \(L_A \ge 2L_B\), where \(L_X\) denotes the length of fish \(X\). There is no fixed rule when a fish will eat another; even if a fish has the ability to eat some smaller fish, it might choose not to do so. A fish may eat several smaller fish one after another. When a fish eats another, its length remains unchanged but the gemstones in the prey’s stomach are transferred intact to the predator.

According to Scheherazade, if you can find this lake, you will be allowed to catch one fish and keep all the gemstones in its stomach. You are curious how many different gemstone combinations you could possibly obtain. Here, a gemstone combination is defined by the counts of each gemstone type (the order in which they appear does not matter, and gems of the same type are indistinguishable).

Write a program that, given the length and initial gemstone type of each fish, determines the number of distinct gemstone combinations that could appear in the stomach of a fish, taken modulo a given integer \(M\).

Note: In any eating sequence, the surviving fish (the one you catch) must be one of the original fish. For it to incorporate the gem of another fish into its stomach, there must be a valid sequence of eatings satisfying the condition \(L_{predator} \ge 2L_{prey}\) at each step. It can be shown that a fish can only possibly eat another fish directly if the other fish’s length is at most half of its own. Thus, if a fish \(r\) is chosen as the final survivor with length \(L_r\), only those fish with \(L \leq \frac{L_r}{2}\) can be incorporated (directly or indirectly) into its gemstone collection.

inputFormat

The first line contains three integers \(F\), \(K\) and \(M\) \((1 \le F \le 20,\ 1 \le K \le F,\ 1 \le M \le 10^9)\) representing the number of fish, the number of gemstone types available, and the modulus.

Then \(F\) lines follow. Each of these lines contains two integers \(L\) and \(G\) \((1 \le L \le 10^9,\ 1 \le G \le K)\) denoting the length of a fish and the type of gemstone it initially swallowed.

Note: It is guaranteed that a fish can eat another only if the latter has length at most half that of the predator. In other words, if a fish of length \(L_r\) is chosen as the final survivor, only fish with lengths satisfying \(2\times L \le L_r\) can be eaten and contribute their gemstone.

outputFormat

Output a single integer: the number of distinct gemstone combinations (multisets defined by gemstone counts) that can appear in the stomach of a fish, modulo \(M\>.

sample

3 2 100
10 1
4 2
2 1

5