AT_abc448_e [ABC448E] Simple Division

整数 $ 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 $ について、以下を繰り返す。 - $ S $ の末尾に数字 $ c_i $ を $ l_i $ 個付け加える。 - 最終的な $ S $ をひとつの整数として解釈したとき、その整数が $ N $ である。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ M $ $ c_1 $ $ l_1 $ $ c_2 $ $ l_2 $ $ \vdots $ $ c_K $ $ l_K $

答えを出力せよ。

### Sample Explanation 1 この入力では $ N=316227766,M=7 $ です。 $ \lfloor 316227766/7 \rfloor = 45175395 $ であり、これを $ 10007 $ で割った余りである $ 3797 $ が最終的な答えとなります。 ### Constraints - $ 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 $ は整数