Problem Description

During the contests Takahashi participated in as a high school student, problems involving the sum of two integers were occasionally given. For the strongest and fastest hands, such problems were a piece of cake.

Now as a university student, Takahashi is participating in a contest for university students with you. However, his preferred integrated development environment (IDE) is broken, and he seems unable to solve the problems. Therefore, as his teammate, you decided to solve the following problem for him until the IDE issue is addressed by the judges.

Given integers \( A \) and \( B \), output the remainder when \( A \) is divided by \( B \). The integers \( A \) and \( B \) have the following characteristics:

• Both integers \( A \) and \( B \) are in decimal (base 10).
• In 99 out of 100 test cases, \( B \) satisfies \( B = 1000000007 \) (\( 10^9 + 7 \)).
• Integer \( A \) is very large and has partial periodicity, given in the following format:
• \( N \) and \( a_1, a_2, ..., a_N \) and \( L_1, L_2, ..., L_N \) are provided. This means that integer \( A \) is formed by repeating \( a_1 \) \( L_1 \) times, \( a_2 \) \( L_2 \) times, ..., and \( a_N \) \( L_N \) times from the highest digit.

For example, when \( N = 3, a = \{123, 4, 56\}, L = \{2, 2, 1\}, B = 1000000007 \), \( A = 1231234456 \), and the remainder when \( A \) is divided by \( B \) is \( 231234449 \).

Input Format

The input is given from the standard input in the following format:

\( N \) \( a_1\ L_1 \) \( a_2\ L_2 \) : \( a_N\ L_N \) \( B \)

• The first line contains an integer \( N \) (\( 1 \leq N \leq 10,000 \)), representing the length of the information about integer \( A \).
• The next \( N \) lines provide the information about integer \( A \). The \( i \)-th line contains \( a_i \) (\( 1 \leq a_i \leq 10^9 \)) and \( L_i \) (\( 1 \leq L_i \leq 10^9 \)) separated by a space.
• The \( N+2 \)-th line contains an integer \( B \) (\( 1 \leq B \leq 1,000,000,007 \)).

Output Format

Output the remainder when \( A \) is divided by \( B \) in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3
123 2
4 2
56 1
1000000007

Sample Output #1

231234449

Sample Input #2

1
123 3
1000000007

Sample Output #2

123123123

Sample Input #3

1
123456789 10000
1000000007

Sample Output #3

372735614

Sample Input #4

4
810143056 100000000
81671422 99999999
1639053 99999998
1657560 99999997
1000000007

Sample Output #4

476685993

Sample Input #5

3
2 3
3 2
5 3
99

Sample Output #5

36

Notes/Hints

Partial Points

This problem has three datasets, each with partial points:

• If you solve dataset 1 where \( L_1 + L_2 + .. + L_N \leq 100,000 \) and \( B = 1000000007 \), you get 20 points.
• If you solve dataset 2 where \( B = 1000000007 \), you get an additional 79 points.
• If you solve dataset 3 without additional constraints, you get an additional 1 point.

Sample Explanation 1

This is the example given in the problem statement.

Sample Explanation 2

\( A = 123123123 \).

Sample Explanation 3

This test case satisfies the constraints of datasets 1, 2, and 3.

Sample Explanation 4

This test case satisfies the constraints of datasets 2 and 3.

Sample Explanation 5

This test case satisfies the constraints of dataset 3.

见题面 Input 部分

见题面 Output 部分