Description

lxhgww loves number games. He discovered that many numbers can be expressed as the sum of two numbers that are reverses of each other; he calls this phenomenon a number’s “mirror decomposition”. For example, $66$ has five mirror decompositions: $66=15+51=24+42=33+33=42+24=51+15$. Note that leading zeros are not allowed, so $66=60+06$ is not counted as a valid mirror decomposition. Now lxhgww wants to know, in base $K$, for the numbers in the interval $[A,B]$, what is the sum of the counts of their mirror decompositions?

Input Format

The first line of input is a number $K$. The second line is a number $n$, denoting the length of the number $A$. The next $n$ lines give each digit of $A$ starting from the least significant digit. Then comes a number $m$, denoting the length of the number $B$. The next $m$ lines give each digit of $B$ starting from the least significant digit.

Output Format

Output one line containing an integer, which is the sum of the counts of mirror decompositions. Since the answer can be very large, output the remainder when this answer is divided by $20110521$.

10
2
6
6
2
6
6

5

Hint

• For $20\%$ of the testdata, it is guaranteed that: $2\le K\le100$, $1\le n,m\le100$.
• For $50\%$ of the testdata, it is guaranteed that: $2\le K\le1000$, $1\le n,m\le1000$.
• For $100\%$ of the testdata, it is guaranteed that: $2\le K\le10^5$, $1\le n,m\le10 ^ 5$.
• For all the testdata, it is guaranteed that: $0\lt A\le B$. Each digit of $A$ and $B$ is in the range $[0, K-1]$, and there are no leading zeros.

Translated by ChatGPT 5