基因突变¶

参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
内存限制：128 MB

背景故事¶

克隆缸的检验完成后，尤里的实验室开始研究基因突变。基因由一串数字表示；突变不改变数字，却改变每一位对能力的贡献。给定标准基因和数值上限，请统计突变后能力超过标准的基因数量。

给定两个进制参数 \(n,m\) .对于非负整数 \(x\) ，将其写成 \(n\) 进制，再把各位的权值从 \(n\) 的幂改为 \(m\) 的幂。若从低位到高位的数字为 \(x_0,\ldots,x_{L-1}\) ，则突变能力为

\[ F(x)=\sum_{i=0}^{L-1}x_i m^i \]

这里 \(0\le x_i<n\) ；即使 \(x_i\ge m\) ，也直接按上式求和，不要求这些数字是合法的 \(m\) 进制数码。

给定标准基因 \(A\) 和上限 \(B\) ，二者均以 \(n\) 进制表示。求满足 \(0\le x\le B\) 且 \(F(x)>F(A)\) 的整数 \(x\) 的数量，对 \(10^9+7\) 取模。前面的大小限制按通常的 \(n\) 进制数值比较，能力则按 \(F\) 比较。

第一行四个整数 \(n,m,L_A,L_B\) .第二行 \(L_A\) 个整数，按从高位到低位给出 \(A\) 的各位。第三行 \(L_B\) 个整数，以同样顺序给出 \(B\) 的各位。

输出一个整数，表示所求数量对 \(10^9+7\) 取模的结果。

10 2 1 3
0
1 0 0

标准能力为零，整数 \(1\) 到 \(100\) 的能力均为正。

10 2 1 2
1
1 0

在 \(0\) 到 \(10\) 中，只有 \(0,1\) 的能力不超过 \(F(A)=1\) ，所以答案为 \(9\) .

10 2 1 3
5
1 0 0

在 \(0\) 到 \(99\) 中，写成十进制 \(10a+b\) 后能力为 \(2a+b\) .其中有 \(6+4+2=12\) 个数的能力不超过 \(5\) ；\(100\) 的能力为 \(4\) ，也不合格，因此有 \(101-13=88\) 个合格整数。

2 3 2 2
1 0
1 1

候选整数为二进制 \(0,1,10,11\) ，能力分别为 \(0,1,3,4\) .只有 \(11\) 的能力严格超过标准 \(10\) 的能力。

分值比例	额外条件
100%	无额外条件