# 基因突变

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 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$ 取模的结果。

## 样例 1

### 输入

```text
10 2 1 3
0
1 0 0
```

### 输出

```text
100
```

### 解释

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

## 样例 2

### 输入

```text
10 2 1 2
1
1 0
```

### 输出

```text
9
```

### 解释

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

## 样例 3

### 输入

```text
10 2 1 3
5
1 0 0
```

### 输出

```text
88
```

### 解释

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

## 样例 4

### 输入

```text
2 3 2 2
1 0
1 1
```

### 输出

```text
1
```

### 解释

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

## 数据范围与保证

- $2\le n,m\le30$ ，$1\le L_A,L_B\le20000$ .
- 所有数码均在 $0$ 到 $n-1$ 之间。
- $A,B$ 无前导零；数字零用单个 $0$ 表示。

### 数据分组

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