← 返回题目列表

AtCoder · arc020_3

C. A mod B 问题

中文机器翻译题面 查看原题

問題文

在高桥高中时参加的一场比赛中,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 的约束。