题目描述

据Scheherazade说，在很远的沙漠中有一个湖。湖中起初有$F$条鱼。选择最值钱的$K$种宝石，对$F$条鱼的每一条只喂给它一块宝石。注意，因为$K$可能小于$F$，两条或更多的鱼可能会吞下同一种宝石。

随着时间的流逝，有些鱼吃掉了别的鱼。一条鱼能够吃掉另一条鱼，当且仅当它的长度至少是被吃掉的鱼的两倍($A$ 能吃掉$B$ 当且仅当$L_A \geq 2L_B$)。没有规则说明一条鱼何时会吃掉另一条鱼。有的鱼可能会一条接一条地吃掉几条小鱼，而有的鱼可能不吃别的鱼，即使它们有能力吃。当一条鱼吃掉一条小鱼时，它的身长并不改变，但是小鱼腹中的宝石会完好无损地进到大鱼腹中。

据Scheherazade说，如果你能够找到那个湖，你会被准许捕捉一条鱼，并且得到鱼腹中的宝石。你很想试试运气，但是在出发前很想知道捉到一条鱼可能会有多少种不同的宝石组合。

写一个程序，给定每条鱼的长度以及其最初吞食的宝石的种类，找出鱼腹中宝石不同组合的数量对给定整数$M$取模的值。组合由每种宝石的数量定义，与宝石的排列顺序无关。同一类宝石中任意两块是没有区别的。

输入格式

你的程序需要从标准输入上读入下列数据：

• 第一行是整数$F$, 即湖中最初鱼的数量。
• 第二行是整数$K$, 即宝石的种类数。不同类型的宝石分别用从 $1$ 到 $K$的整数表示。
• 第三行是整数$M$。
• 以后 $F$ 行中的每一行用由一个空格分隔的两个整数描述一条鱼：按顺序分别是鱼的长度以及鱼腹中的宝石的类型。

注意: 在所有的测试用例中，$K$ 种宝石中的每一种都会至少有一块。

输出格式

你的程序需要在标准输出上输出一个介于$0$和$M-1$(包含)的整数，即宝石所有可能的不同组合数量模$M$，占一行。注意，在问题求解中，数值$M$除了简化计算外没有其他的作用。

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

4

提示

限制

有总计70分的测试数据，其中$K$不超过$7,000$。在这些测试数据中，有总计25分的测试数据的$K$不超过$20$。

对于所有的测试数据，$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$。

样例说明

有 $11$ 种可能的组合，所以你需要输出$4$，也就是$11$ 模 $7$。这些可能的组合是: $[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]$: 第三条鱼吃掉第五条鱼，你捉到了第三条鱼。