Background

2025-04-10: The incorrect testdata in the problem was removed.

Problem Description

A base determines when a carry happens on each digit position.

The $X$ base is a special kind of base, because the base of each digit position is not fixed. For example, for some $X$-base number, the lowest digit position is base $2$, the second digit position is base $10$, and the third digit position is base $8$. Then the $X$-base number 321 converts to the decimal number 65.

Now there are two integers $A$ and $B$ written in $X$ base, but the exact base of each digit position is still unknown. The only things known are that $A$ and $B$ follow the same base rule, and that for each digit position, the maximum base is $N+1$ and the minimum base is $2$. Please compute the minimum possible value of $A-B$.

Note that you must ensure that both $A$ and $B$ are valid in $X$ base, i.e., the digit on each position must be smaller than its base.

Input Format

The first line contains a positive integer $N$, with the meaning as described above.

The second line contains a positive integer $M_{a}$, the number of digits of the $X$-base number $A$.

The third line contains $M_{a}$ integers separated by spaces, representing the digits of $A$ in decimal, from the most significant digit to the least significant digit.

The fourth line contains a positive integer $M_{b}$, the number of digits of the $X$-base number $B$.

The fifth line contains $M_{b}$ integers separated by spaces, representing the digits of $B$ in decimal, from the most significant digit to the least significant digit.

Note that all numbers in the input are in decimal.

Output Format

Output one line containing one integer, which is the minimum possible value of $A-B$ in $X$ base, converted to decimal and then taken modulo $1000000007$ (i.e., $10^9+7$).

11
3
10 4 0
3
1 2 0

94

Hint

Sample Explanation

When the bases are: base $2$ for the lowest digit, base $5$ for the second digit, and base $11$ for the third digit, the subtraction gives the minimum difference. In this case, $A$ is $108$ in decimal, $B$ is $14$ in decimal, and the difference is $94$.

Constraints and Notes

For $30\%$ of the data, $N \leq 10$, $M_{a}, M_{b} \leq 8$.

For $100\%$ of the data, $2 \leq N \leq 1000$, $1 \leq M_{a}, M_{b} \leq 10^5$, $A \geq B$.

Lanqiao Cup 2022 Provincial Contest B Group, Problem E.

Translated by ChatGPT 5