公共子序列

题目描述

给定由 $1$ 到 $10^5$ 之间的整数组成、长度为 $N$ 的整数序列 $S$ 和长度为 $M$ 的整数序列 $T$。

有多少对 $S$ 的子序列和 $T$ 的子序列,使得它们作为整数序列相等?

这里,整数序列 $A$ 的子序列是指:从 $A$ 中删除 $0$ 个或多个元素,把剩余的元素保持原有顺序排成的整数序列。

另外,即使 $S, T$ 各自的子序列作为整数序列相等,只要被删除元素的下标集合不同,就区分为不同的子序列。

答案可能非常大,请输出它除以 $10^9+7$ 的余数。

输入格式

输入按以下格式从标准输入给出:

$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)$ 的组有 $1 \times 1$ 种,同为 $(3)$ 的组有 $1 \times 1$ 种,所以共有 $3$ 种。

2 2
1 1
1 1

6

$S$ 的子序列有 $(), (1), (1), (1, 1)$。

$T$ 的子序列有 $(), (1), (1), (1, 1)$。

子序列同为 $()$ 的组有 $1 \times 1$ 种,同为 $(1)$ 的组有 $2 \times 2$ 种,同为 $(1, 1)$ 的组有 $1 \times 1$ 种,所以共有 $6$ 种。

注意:子序列中因删除元素下标集合不同而区分的子序列也要加以区分。

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$ 的余数。

数据范围

• $1 \le N, M \le 2 \times 10^3$
• $S$ 的长度为 $N$
• $T$ 的长度为 $M$
• $1 \le S_i, T_i \le 10^5$
• 输入均为整数