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

输入

2 2
1 3
3 1

输出

3

样例 2

输入

2 2
1 1
1 1

输出

6

样例 3

输入

4 4
3 4 5 6
3 4 5 6

输出

16

样例 4

输入

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

输出

191

样例 5

输入

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

说明/提示

限制条件

• $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 翻译