問題文
在高桥高中时参加的一场比赛中,2 我曾经被问过一个关于求两个整数之和的问题。在最强、速度最快的人手中,这样的事情简直微不足道。
已成为大学生的高桥目前正在和你一起参加大学生竞赛。然而,使用他最喜欢的语言所需的集成开发环境坏了,他似乎无法解决这个问题。 作为队友,你决定为他解决以下问题,直到裁判解决了集成开发环境问题。 打印除以
整数 A 和 将其放在 B 。 来自行 A 请计算 B 后的余数。然而,整数 A 和整数 B 具有以下特点。
- 整数 A, B 都是 10 这是一个基数。
- 整数 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
- 1 行包含以下整数 表示 A 信息长度的整数 在 N (1 ≦ N ≦ 10,000) 。 来自行
- 2 第 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) 。 来自行
部分点
这个问题有3个数据集,每个数据集都设置了部分点。
- L_1+L_2+..+L_N ≦ 100,000 并且, 如果您对满足B=1000000007 的数据集 1 的回答正确 如果您对满足 20 分被给予。
- B=1000000007 的数据集 2 的回答正确,那么 79 分被给予。
- 如果您在没有附加约束的情况下正确回答了数据集 3,则 在 1 分被给予。
出力
A 请计算 B 取模之后的余数 1 行输出。在输出末尾插入换行符。
入力例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 的约束。