T156618 「MCOI-(-1)」游戏编码

我们都知道 MC 是用编码形成的游戏，编码可以看做一些字符串用一些空格和换行组成的。 今天，Steve 和 Alex 在 MC 世界里待的无聊了，所以打算把 MC 源代码作为字符串来玩玩。 Steve 和 Alex 无意间听到了哈希值的定义，所以 Steve 就像让 Alex 计算一些哈希值。

已知一个字符串为 $S$，$\rm Len$ 表示它的长度，它的第 $i$ 位的 ASCII 码为 $S_i$。 字符串 $S$ 的哈希值 $H(S)$ 定义为： $$H(S)=\sum\limits_{i=1}^{\rm Len}S_i\times R^{{\rm Len}-i}$$ 当然哈希值还需要对 $P$ 取模。其中 $R$ 是一个选定的底数，是一个定值。 举个例子，已知字符串 $S=\tt abc$，$R=131$，$P=10^4+7$，则它的哈希值 $H(S)$ 为： $$H(S)=97\times 131^2+99\times131+98=1677682$$ $\bmod\ P$ 后值为 $6515$。 但 Alex 不满足于字符串哈希，他还会数列哈希。与字符串哈希相似，对于数列 $S$，$\rm Len$ 表示它的长度，$S_i$ 表示第 $i$ 个元素的值，$H(S)$ 定义为： $$H(S)=\sum\limits_{i=1}^{\rm Len}S_i\times R^{{\rm Len}-i}$$ 结果对 $P$ 取模。 举个例子，已知数列 $S=\{97,99,98\}$，$R=131$，$P=10^4+7$，则它的哈希值 $H(S)$ 为 $$H(S)=97\times 131^2+99\times131+98=1677682$$ $\bmod\ P$ 后值为 $6515$。 Alex 很高兴，它试图将它见到的所有字符串进行哈希。 一旁的 Steve 看不下去了，它扔给 Alex 一个特别的数列。 这个数列由 $N$ 段构成，第 $i$ 段由相同的 $C_i$ 个数 $A_i$ 构成。比如 $N=2,C_1=3,A_1=2,C_2=5,A_2=3$，那么数列为 $\{2,2,2,3,3,3,3,3\}$。 Alex 花了很长时间仍然没有算出它的哈希值，他现在向你求助，他需要你帮他计算这个数列的哈希值。由于 Alex 并不会判断一个数是否为质数，所以不保证 $P$ 为质数。

第一行三个正整数 $N,P,R$，分别表示数列的段数，哈希的模数和底数 $R$。 接下来 $N$ 行，每行两个正整数，分别对应 $C_i,A_i$。

输出仅一行，即取模后的哈希值 $H(S)$。

#### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（10 pts）：$N,C_i \le 1000$，满足性质 A。 - Subtask 2（25 pts）：满足性质 A。 - Subtask 3（30 pts）：$N \le 10^5$。 - Subtask 4（35 pts）：无特殊限制。 对于 $100\%$ 的数据，$1 \le N\le 10^6$，$1\le C_i\lt2^{63}$，$1 \le P,A_i\le2^{31}$。 性质 A：Alex 运气好，$P$ 为质数。 Subtask 1 ~ 3 时限 1s，Subtask 4 时限 3s。