P4684 [IOI 2008] Fish

题目描述

据 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$（包含 $0$ 和 $M-1$）的整数，即宝石所有可能的不同组合数量模 $M$，占一行。注意，在问题求解中，数值 $M$ 除了简化计算外没有其他的作用。

输入输出样例 #1

输入 #1

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

输出 #1

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]$：第三条鱼吃掉第五条鱼，你捉到了第三条鱼。