AT_abc130_e [ABC130E] Common Subsequence

给定一个由 $1$ 到 $10^5$ 之间的整数构成的长度为 $N$ 的整数列 $S$ 和一个长度为 $M$ 的整数列 $T$。 请计算有多少对 $S$ 的子序列和 $T$ 的子序列，使得它们作为整数列是相等的。 这里，整数列 $A$ 的子序列是指，从 $A$ 中选择若干（可以为 $0$ 个）元素删除，剩下的元素按照原顺序排列所得到的整数列。 另外，即使 $S$ 和 $T$ 的子序列作为整数列相等，只要删除的元素下标集合不同，也要将其视为不同的子序列。 由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。

输入以如下格式从标准输入给出。 > $N$ $M$ $S_1$ $S_2$ $\ldots$ $S_{N}$ $T_1$ $T_2$ $\ldots$ $T_{M}$

请输出作为整数列相等的 $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$ - 输入均为整数 ## 样例解释 1 $S$ 的子序列有 $(),\ (1),\ (3),\ (1, 3)$。$T$ 的子序列有 $(),\ (3),\ (1),\ (3, 1)$。两者都为 $()$ 的组合有 $1 \times 1$ 种，都为 $(1)$ 的组合有 $1 \times 1$ 种，都为 $(3)$ 的组合有 $1 \times 1$ 种，因此共有 $3$ 种组合。 ## 样例解释 2 $S$ 的子序列有 $(),\ (1),\ (1),\ (1, 1)$。$T$ 的子序列有 $(),\ (1),\ (1),\ (1, 1)$。两者都为 $()$ 的组合有 $1 \times 1$ 种，都为 $(1)$ 的组合有 $2 \times 2$ 种，都为 $(1, 1)$ 的组合有 $1 \times 1$ 种，因此共有 $6$ 种组合。请注意，对于子序列，删除元素的下标集合不同的情况要区分开来。 ## 样例解释 5 请注意输出时需要对 $10^9+7$ 取模。 由 ChatGPT 4.1 翻译