问题文

高桥君在高中时参加的比赛中，出现了求两个整数的和的问题。如果对最强最快的人来说，这种问题简直轻而易举。

成为大学生的高桥君目前正在参加面向大学生的比赛，然而，他经常使用的集成开发环境遭到了损坏，似乎无法解决问题。因此，作为他的队友，你决定在集成开发环境的问题得到裁判组的解决之前，代替他解决以下问题。

给定整数 $A$ 和 $B$。请输出 $A$ 除以 $B$ 的余数。但是，整数 $A$ 和整数 $B$ 具有以下特点：

• 整数 $A$，$B$ 都是十进制数。

• 整数 $B$ 在 100 个测试用例中的 99 个测试用例中满足 $B=1000000007(10^9+7)$。

• 整数 $A$ 非常大，且部分具有周期性，以以下形式给出：

• 给定 $N$，$a_1,a_2,..,a_N$ 和 $L_1,L_2,..,L_N$。这表示整数 $A$ 的形式是从上面的位开始，重复 $a_1$ 重复 $L_1$ 次，$a_2$ 重复 $L_2$ 次，..，$a_N$ 重复 $L_N$ 次。

例如，当 $N=3,a=\\{123,4,56\\},L=\\{2,2,1\\},B=1000000007$ 时，$A=1231234456$，$A$ 除以 $B$ 的余数为 $231234449$。

---

输入

输入以以下格式从标准输入中给出。

$N$ $a_1\\ L_1$ $a_2\\ L_2$ : $a_N\\ L_N$ $B$

• 第一行是一个整数 $N$，表示后面的整数 $A$ 的长度 $(1 ≦ N ≦ 10,000)$。
• 接下来的 $N$ 行中，给出了整数 $A$ 的信息。其中第 $i$ 行包含问题描述中的 $a_i (1 ≦ a_i ≦ 10^9)$ 和 $L_i (1 ≦ L_i ≦ 10^9)$，以半角空格分隔。
• 第 $N+2$ 行给出了整数 $B (1 ≦ B ≦ 1,000,000,007)$。

---

部分点

该问题有三个数据集，每个数据集都有相应的部分得分。

• 如果满足 $L_1+L_2+..+L_N ≦ 100,000$ 且 $B=1000000007$ 的数据集 1 得到正确答案，则获得 20 分。
• 如果满足 $B=1000000007$ 的数据集 2 得到正确答案，则获得除上述数据集之外的额外 79 分。
• 如果满足无其他约束条件的数据集 3 得到正确答案，则获得除上述数据集之外的额外 1 分。

---

输出

请在一行中输出 $A$ 除以 $B$ 的余数。输出末尾要换行。

---

示例输入1

3
123 2
4 2
56 1
1000000007

示例输出1

231234449

这是问题文中的示例。

---

示例输入2

1
123 3
1000000007

示例输出2

123123123

$A=123123123$。

---

示例输入3

1
123456789 10000
1000000007

示例输出3

372735614

该测试用例满足数据集 1、2 和 3 的约束。

---

示例输入4

4
810143056 100000000
81671422 99999999
1639053 99999998
1657560 99999997
1000000007

示例输出4

476685993

该测试用例满足数据集 2 和 3 的约束。

---

示例输入5

3
2 3
3 2
5 3
99

示例输出5

36

该测试用例满足数据集 3 的约束。

---