题目描述

进制规定了数字在数位上逢几进一。

$X$进制是一种很神奇的进制，因为其每一数位的进制并不固定！按理说某种$X$进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则$X$​进制数321转换成十进制数为65。

小tips:X 进制数的第 i 位的权值 = 低位进制之积

$$3 \times 2 \times 10 + 2 \times 2 + 1 \times 1 = 65 $$

现在有两个$X$进制表示的整数$A$和$B$，但是其具体每一数位的进制还不确定， 只知道$A$和$B$是同一进制规则，且每一数位最高为$N$进制，最低为二进制，请你计算出$A - B$的结果的最小可能是多少。

请注意，你需要保证$A$和$B$在$x$进制下都是合法的，即每一数位上的数字要小于其进制。

输入格式

第一行一个正整数$N$，含义如题面所述。

第二行一个正整数$M_a$，表示$X$进制数$A$的位数。

第三行$M_a$个用空格分开的整数，表示$X$进制数$A$按从高位到地位顺序各个数位上的数字在十进制下的表示。

第四行一个正整数$M_b$,表示$X$进制数$B$的位数。

第五行$M_b$个用空格分开的整数，表示$X$进制数$B$​按从高位到地位顺序各个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

输出格式

输出一行一个整数， 表示$X$进制数$A-B$的结果的最小可能值转换为十进制后再模1000000007的结果。

样例输入输出

11
3
10 4 0
3
1 2 0

94

样例说明

当进制为：最低位2进制， 第二数位5进制， 第三数位11进制时，减法得到的差最小。此时$A$在十进制下是108， $B$在十进制下是14， 差值是94。

评测用例规模与规定

对于$50\%$的评测样例,$N \leqslant 10;M_a, M_b \leqslant 8$。

对于$100\%$的评测样例，$2\leqslant N \leqslant 1000;1 \leqslant M_a, M_b \leqslant 100000; A\geqslant B$​。

运行限制

• 最大运行时间：$1s$
• 最大运行内存：$256M$