E - 公共子序列

分数：500 分

问题描述

给定两个整数序列 $S$ 和 $T$，长度分别为 $N$ 和 $M$，均由介于 $1$ 和 $10^5$ (含)之间的整数组成。

请计算在多少对 $S$ 和 $T$ 的子序列中，两个子序列的内容相同。

这里所说的子序列是指通过从原序列中移除零个或多个元素，并按原顺序连接剩余元素所得到的序列。

对于 $S$ 和 $T$，即使两个子序列的内容相同，如果移除元素的索引集合不同，我们也认为这两个子序列是不同的。

由于答案可能非常大，因此请输出对 $10^9+7$ 取模后的结果。

约束条件

• $1 \leq N, M \leq 2 \times 10^3$
• 序列 $S$ 的长度为 $N$。
• 序列 $T$ 的长度为 $M$。
• $1 \leq S_i, T_i \leq 10^5$
• 输入中的所有值均为整数。

输入

从标准输入读入以下内容：

$N$ $M$

$S_1$ $S_2$ $...$ $S_{N-1}$ $S_{N}$

$T_1$ $T_2$ $...$ $T_{M-1}$ $T_{M}$

输出

打印满足条件的 $S$ 和 $T$ 的子序列对数，对 $10^9+7$ 取模后的结果。

2 2
1 3
3 1

3

$S$ 有四个子序列：$(), (1), (3), (1, 3)$。

$T$ 也有四个子序列：$(), (3), (1), (3, 1)$。

有 $1 \times 1$ 对子序列，其中两个子序列都是 $()$，
有 $1 \times 1$ 对子序列，其中两个子序列都是 $(1)$，
也有 $1 \times 1$ 对子序列，其中两个子序列都是 $(3)$，总计三对。

2 2
1 1
1 1

6

$S$ 有四个子序列：$(), (1), (1), (1, 1)$。

$T$ 也有四个子序列：$(), (1), (1), (1, 1)$。

有 $1 \times 1$ 对子序列，其中两个子序列都是 $()$，
有 $2 \times 2$ 对子序列，其中两个子序列都是 $(1)$，
以及有 $1 \times 1$ 对子序列，其中两个子序列都是 $(1,1)$，总计六对。
请注意，即使两个子序列的内容相同，如果移除元素的索引集合不同，我们也认为这两个子序列是不同的。

4 4
3 4 5 6
3 4 5 6

16

10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

191

20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

846527861

请务必打印对 $10^9+7$ 取模后的结果。