lxhgww is very fond of number games. He discovered that many numbers can be represented as the sum of two numbers that are reversals of each other. He calls this phenomenon "mirror splitting." For example, $66$ has five mirror splitting methods:

66=15+51   
66=24+42  
66=33+33  
66=42+24  
66=51+15

Note that leading zeros are not allowed, so $66=60+06$ is not considered a valid mirror split.

Now, lxhgww wants to know the total number of mirror splitting ways for all numbers in the range $[A, B]$ in base $K$.

Input

The first line contains a number $K$.

The second line contains a number $n$, representing the length of the number $A$.

The next $n$ lines represent each digit of $A$, starting from the least significant digit.

Then there is a number $m$, representing the length of the number $B$.

The next $m$ lines represent each digit of $B$, starting from the least significant digit.

Output

Output a single line containing an integer representing the total number of mirror splitting ways. Since this answer can be very large, output the answer modulo $20110521$.

Examples

Input 1

10
2
6
6
2
6
6

Output 1

5

Input 2

10
1
1
4
0
0
0
1

Output 2

410

Subtasks

For $20\%$ of the data, $2 \le K \le 100$, $1 \le n, m \le 100$.

For $50\%$ of the data, $2 \le K \le 10^3$, $1 \le n, m \le 10^3$.

For $100\%$ of the data, $2 \le K \le 10^5$, $1 \le n, m \le 10^5$.

For all data, $0 < A \leq B$, and each digit of $A$ and $B$ is in the range $[0, K-1]$, with no leading zeros.