AT_arc020_3 [ARC020C] A mod B Problem

[problemUrl]: https://atcoder.jp/contests/arc020/tasks/arc020_3 高橋君が高校生の頃参加していたコンテストでは、$ 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) $ が与えられる。

$ A $ を $ B $ で割った余りを $ 1 $ 行に出力せよ。出力の末尾に改行をいれること。

### 部分点 この問題には3つのデータセットがあり、データセット毎に部分点が設定されている。 - $ L_1+L_2+..+L_N\ ≦\ 100,000 $ かつ、$ B=1000000007 $ を満たすデータセット 1 に正解した場合は $ 20 $ 点が与えられる。 - $ B=1000000007 $ を満たすデータセット 2 に正解した場合は、上記のデータセットとは別に $ 79 $ 点が与えられる。 - 追加制約のないデータセット 3 に正解した場合は、上記のデータセットとは別に $ 1 $ 点が与えられる。 ### Sample Explanation 1 問題文中の例です。 ### Sample Explanation 2 $ A=123123123 $ です。 ### Sample Explanation 3 このテストケースはデータセット 1,2,3 の制約を満たしています。 ### Sample Explanation 4 このテストケースはデータセット 2,3 の制約を満たしています。 ### Sample Explanation 5 このテストケースはデータセット 3 の制約を満たしています。