4990：基因序列
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：1
解决：0
题目描述
# 基因序列
## 题目描述
在生物信息学研究中，研究员常需要比较两段基因序列的相似度。现有两段由核苷酸编号组成的序列 $A$ 和 $B$ ，长度分别为 $N$ 和 $M$ 。序列中的每个元素都是一个 $[1, 10^5]$ 之间的整数。
在比对过程中，研究员会从序列 $A$ 中选出一个子序列 $A'$ ，再从序列 $B$ 中选出一个子序列 $B'$ 。
如果子序列 $A'$ 与子序列 $B'$ 完全相同（即长度相同且对应位置的元素相等），则称其为一对“匹配子序列对”。
需要注意的是：
- **下标敏感**：即使两个子序列所含的元素数值序列相同，只要选取的元素在原序列中的下标集合不同，就视为不同的子序列。
- **空序列**：根据研究定义，从 $A$ 和 $B$ 中均不选取任何元素所构成的空序列对，也算作一对匹配子序列对。
- **子序列**：从原序列中选择若干元素（可以不选），在不改变它们相对前后顺序的前提下，提取出来所组成的新序列。
请你编写程序，计算两段序列中共有多少对不同的“匹配子序列对”。由于答案可能很大，请输出对 $10^9 + 7$ 取模后的结果。
## 输入格式
第一行包含两个整数 $N$ 和 $M$ ，分别表示序列 $A$ 和 $B$ 的长度。
第二行包含 $N$ 个整数，表示序列 $A$ 的各个元素。
第三行包含 $M$ 个整数，表示序列 $B$ 的各个元素。
## 输出格式
输出一个整数，表示匹配子序列对的总数对 $10^9 + 7$ 取模后的结果。
## 样例
### 样例输入 1
```text
2 2
1 3
3 1
```
### 样例输出 1
```text
3
```
### 样例输入 2
```text
2 2
1 1
1 1
```
### 样例输出 2
```text
6
```
### 样例输入 3
```text
4 4
3 4 5 6
3 4 5 6
```
### 样例输出 3
```text
16
```
## 说明/提示
输入样例 4
10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7
输出样例 4
191
**样例 1 说明：**
- $A$ 的子序列有： $\emptyset, (1), (3), (1,3)$ ；
- $B$ 的子序列有： $\emptyset, (3), (1), (3,1)$ 。
匹配的子序列对为： $(\emptyset, \emptyset)$ 、 $((1), (1))$ 、 $((3), (3))$ ，共 3 对。
**样例 2 说明：**
$A$ 有两个位置可以选出 $(1)$ ，记为 $A_1, A_2$ ； $B$ 同理记为 $B_1, B_2$ 。 匹配对如下：
- 空序列匹配： $(\emptyset, \emptyset)$ ，共 $1$ 对；
- 长度为 1 的匹配： $(A_1, B_1), (A_1, B_2), (A_2, B_1), (A_2, B_2)$ ，共 $4$ 对；
- 长度为 2 的匹配： $((A_1, A_2), (B_1, B_2))$ ，共 $1$ 对。 总计 $1 + 4 + 1 = 6$ 对。
数据范围
| 测试点编号 | $N,M$ |
|---|---|
| $1 \sim 5$ | $1 \le N,M \le 50$ |
| $6 \sim 25$ | $1 \le N \le 2000$ |
对于 $100\%$ 的数据，满足 $1 \leq N, M \leq 2000$ ， $1 \leq A_i, B_i \leq 10^5$ 。
---
**题目来源：** 26年3月-B组（才俊）