C - A mod B Problem Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君が高校生の頃参加していたコンテストでは、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 の制約を満たしています。