Description

Fish is a fish living in the sea. One day he felt bored and started a counting game. The detailed rules are:

1. Fix a base $B$ for counting.

2. Fix an interval $[L, R]$.

3. For each number in $[L, R]$, regard the number as a string, and list the value in base $B$ of each (contiguous) substring of that string.

4. Sum all the listed numbers. Now Fish has finished one round of counting, but he is not sure whether his result is correct. Since $[L, R]$ is large, he does not have the extra energy to verify it. Can you write a program to help him verify it?

Input Format

The input contains three lines.

The first line contains only one number $B$, which is the base for counting.

The second line contains $N+1$ numbers. The first number is $N$, meaning that the length of $L$ in base $B$ is $N$. The next $N$ numbers, from the most significant digit to the least significant digit, represent each digit of $L$.

The third line contains $M+ 1$ numbers. The first number is $M$, meaning that the length of $R$ in base $B$ is $M$. The next $M$ numbers, from the most significant digit to the least significant digit, represent each digit of $R$.

Output Format

Output exactly one line: the result according to Fish’s counting rules, expressed in base $10$. Since the number can be large, output the result modulo $20130427$.

In the testdata, there may be cases where $r<l$. In such cases, the output is $-ans[r+1,l-1]\bmod 20130427$.

10
3 1 0 3
3 1 0 3

120

Hint

Sample Explanation:

$[103, 103]$ contains only the number 103. All its substrings include 1, 10, 103, 0, 03, 3, and their sum is 120.

Constraints:

$20\%$ of the testdata: $0 \le L \le R \le 10^5$.

$50\%$ of the testdata: $2 \le B \le 1000, 1 \le N, M \le 1000$.

$100\%$ of the testdata: $2 \le B \le 10^5, 1 \le N, M \le 10^5$.

Translated by ChatGPT 5