题目描述

Kitten 给了 33DAI 两个个整数 $a$ 和 $b$，并要求 33DAI 计算出 $a \bmod b$。

为了让这道题变得更困难，Kitten 会给出一个特别大的 $a$，然后告诉 33DAI 这个 $a$ 压缩后的形式。

$a$ 的压缩形式包括 $n$ 段，第 $i$ 段表示 $a$ 从高到低的第 $i$ 部分，用 $x_i, y_i$ 描述，指的是这一段为 $y_i$ 次的 $x_i$ 重复形成。比如当 $x_i=233,y_i=4$ 时就表示 $233233233233$

请你帮帮可怜的 33DAI 吧。

输入格式

输入第一行为一个整数 $n$

接下来 $n$ 行，第 $i$ 行为 $x_i,y_i$

接下来一行为整数 $b$

输出格式

一行一个整数，为 $a \bmod b$ 的结果。

3
123 2
4 2
56 1
1000000007

231234449

样例 1 解释

$1231234456 \bmod 1000000007 = 231234449$

1
123 3
1000000007

123123123

1
123456789 10000
1000000007

372735614

4
810143056 100000000
81671422 99999999
1639053 99999998
1657560 99999997
1000000007

476685993

3
2 3
3 2
5 3
99

36

大样例：sample2.zip

数据规模与约定

对于 $100\%$ 的数据：

• $1\ \le \ n\ \le \ 10,000$。
• $1\ \le \ x_i\ \le \ 10^9$，$1\ \le\ y_i\ \le\ 10^9$
• $1\ \le \ b\ \le \ 1,000,000,007$

子任务：

• 子任务 1（10 分）：$a$ 的位数小于等于 $18$
• 子任务 1（30 分）：$a$ 的位数小于等于 $10^5$
• 子任务 2（30 分）：所有 $x_i$ 都是一位数，即 $1\le x_i\le 9$。
• 子任务 3（30 分）：没有特殊限制