AT_abc448_e [ABC448E] Simple Division

You are given integers $ N $ and $ M $ . Find the remainder when $ \lfloor N/M \rfloor $ is divided by $ \color{red}{10007} $ . Here, $ \lfloor x \rfloor $ denotes the largest integer not exceeding $ x $ . For example, $ \lfloor 3.14 \rfloor=3 $ and $ \lfloor 10 \rfloor = 10 $ . In this problem, $ N $ is not given directly; instead, it is given in run-length encoded form. Specifically, $ N $ is represented by a sequence of $ K $ pairs of a digit $ c_i $ and an integer $ l_i $ . To recover the original $ N $ , use the following procedure. - Initially, let string $ S $ be the empty string. - For $ i=1,2,\dots,K $ , repeat the following. - Append $ l_i $ copies of digit $ c_i $ to the end of $ S $ . - Interpret the final $ S $ as a single integer; that integer is $ N $ .

The input is given from Standard Input in the following format: > $ K $ $ M $ $ c_1 $ $ l_1 $ $ c_2 $ $ l_2 $ $ \vdots $ $ c_K $ $ l_K $

Output the answer.

### Sample Explanation 1 In this input, $ N=316227766 $ and $ M=7 $ . $ \lfloor 316227766/7 \rfloor = 45175395 $ , and the remainder when this is divided by $ 10007 $ is $ 3797 $ , which is the final answer. ### Constraints - $ 1 \le M \le 10^4 $ - $ 1 \le K \le 10^5 $ - $ c_i $ is one of the digits $ 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 $ are integers.