相传在遥远的沙漠中央有一片湖泊。最初，湖里有 $F$ 条鱼。在地球上最珍贵的宝石中挑选出了 $K$ 种不同的宝石，每条鱼都吞下了一颗宝石。注意，由于 $K$ 可能小于 $F$，因此两条或多条鱼可能吞下了同种宝石。

随着时间的推移，一些鱼吃掉了另一些鱼。当且仅当一条鱼的长度至少是另一条鱼的两倍时，它才能吃掉对方（鱼 $A$ 可以吃掉鱼 $B$，当且仅当 $L_A \ge 2 \times L_B$）。关于鱼何时进食并没有规则。一条鱼可能决定连续吃掉几条较小的鱼，而有些鱼即使有能力进食，也可能选择不吃任何鱼。当一条鱼吃掉较小的鱼时，它的长度不会改变，但被吃掉的鱼胃里的宝石会完好无损地进入大鱼的胃里。

谢赫拉莎德（Scheherazade）说，如果你能找到这片湖泊，你将被允许捞出一条鱼，并保留它胃里的所有宝石。你打算碰碰运气，但在踏上漫长的旅程之前，你想知道通过捕获一条鱼，你总共能获得多少种不同的宝石组合。

题目描述

编写一个程序，给定每条鱼的长度以及每条鱼最初吞下的宝石种类，计算任何一条鱼胃里最终可能存在的宝石组合总数，结果对给定的整数 $M$ 取模。组合仅由 $K$ 种宝石中每种宝石的数量定义。宝石之间没有顺序之分，且同种宝石无法区分。

数据范围

$1 \le F \le 500,000$：湖中最初的鱼的数量。 $1 \le K \le F$：宝石种类的数量。 $2 \le M \le 30,000$ $1 \le L_X \le 1,000,000,000$：鱼 $X$ 的长度。

输入格式

程序必须从标准输入读取以下数据： 第 1 行包含整数 $F$，即湖中最初的鱼的数量。 第 2 行包含整数 $K$，即宝石种类的数量。宝石种类用 $1$ 到 $K$ 的整数表示。 第 3 行包含整数 $M$。 接下来的 $F$ 行，每行描述一条鱼，包含两个由空格分隔的整数：鱼的长度，以及该鱼最初吞下的宝石种类。

注意：对于所有用于评估的测试用例，保证每种宝石至少出现一次。

输出格式

程序必须向标准输出写入一行，包含一个 $0$ 到 $M-1$（含）之间的整数：不同宝石组合的总数对 $M$ 取模的结果。 注意，对于解决本题而言，$M$ 的值除了简化计算外没有其他意义。

子任务

对于总分 70 分的若干测试用例，$K$ 不超过 7,000。 此外，对于总分 25 分的某些测试用例，$K$ 不超过 20。

样例

样例输入 1

5 
3 
7 
2 2 
5 1 
8 3 
4 1 
2 3

样例输出 1

4

说明

共有 11 种可能的组合，因此你应该输出 $11 \pmod 7$，即 4。

可能的组合为：[1]、[1,2]、[1,2,3]、[1,2,3,3]、[1,3]、[1,3,3]、[2]、[2,3]、[2,3,3]、[3] 和 [3,3]。（对于每个组合，我们列出它包含的宝石。例如，[2,3,3] 是一个由一颗 2 号宝石和两颗 3 号宝石组成的组合。）

这些组合可以通过以下方式实现： [1]：你可能在第二条（或第四条）鱼吃掉任何其他鱼之前就捕获了它。 [1,2]：如果第二条鱼吃掉了第一条鱼，那么它将拥有一颗 1 号宝石（它最初吞下的）和一颗 2 号宝石（来自第一条鱼的胃里）。 [1,2,3]：达到此组合的一种可能方式：第四条鱼吃掉第一条鱼，然后第三条鱼吃掉第四条鱼。如果你现在捕获第三条鱼，它的胃里将各有一颗每种宝石。 [1,2,3,3]：第四条吃掉第一条，第三条吃掉第四条，第三条吃掉第五条，你捕获第三条。 [1,3]：第三条吃掉第四条，你捕获它。 [1,3,3]：第三条吃掉第五条，第三条吃掉第四条，你捕获它。 [2]：你捕获第一条鱼。 [2,3]：第三条吃掉第一条，你捕获它。 [2,3,3]：第三条吃掉第一条，第三条吃掉第五条，你捕获它。 [3]：你捕获第三条鱼。 * [3,3]：第三条吃掉第五条，你捕获它。