← 返回题目列表

AtCoder · abc448_e

H. 简单除法

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

分数: 450 点

问题陈述

给你整数 N 和 M。求余数,当 \lfloor N/M \rfloor 除以 \color{red}{10007}.
在这里, \lfloor x \rfloor 表示不超过的最大整数 x。例如, \lfloor 3.14 \rfloor=3 和 \lfloor 10 \rfloor = 10.

在这个问题中, N 没有直接给出;相反,它以游程编码形式给出。
具体来说, N 由一系列表示 K 一对数字 c_i 和一个整数 l_i.
恢复原始 N,使用以下过程。

  • 首先,让字符串 S 是空字符串。
  • 对于 i=1,2,\dots,K,重复以下操作。
    • 追加 l_i 数字副本 c_i 到年底 S.
  • 最终解读 S 作为单个整数;该整数是 N.

约束

  • 1 \le M \le 10^4
  • 1 \le K \le 10^5
  • c_i 是数字之一 0,1,2,3,4,5,6,7,8,9.
  • 1 \le l_i \le 10^9
  • c_1 \neq 0
  • M,K,l_i 是整数。

输入

输入由标准输入按以下格式给出:

K M
c_1 l_1
c_2 l_2
\vdots
c_K l_K

输出

输出答案。


示例输入 1

6 7
3 1
1 1
6 1
2 2
7 2
6 2

示例输出 1

3797

在此输入中, N=316227766 和 M=7.
\lfloor 316227766/7 \rfloor = 45175395,以及除以的余数 10007 is 3797,这是最终的答案。


示例输入 2

1 1
1 1

示例输出 2

1

示例输入 3

10 9999
9 419921892
9 923650333
6 476449815
1 8837775
2 141135534
5 462618481
3 202652735
0 771538044
4 321458589
0 570032864

示例输出 3

8437