该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

E - 公共子序列

分数：500分

问题描述

给定两个整数序列$S$和$T$，长度分别为$N$和$M$，均由$1$到$10^5$（含）之间的整数组成。 有多少对$S$的子序列和$T$的子序列在内容上是相同的？ 这里，$A$的子序列是指通过从$A$中移除零个或多个元素，并按原顺序连接剩余元素得到的序列。 对于$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$取模。

样例输入1

2 2

1 3

3 1

样例输出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 2

1 1

1 1

样例输出2

6

$S$有四个子序列：$()$、$(1)$、$(1)$、$(1, 1)$。 $T$有四个子序列：$()$、$(1)$、$(1)$、$(1, 1)$。 有$1 \times 1$对子序列均为$()$，$2 \times 2$对子序列均为$(1)$，$1 \times 1$对子序列均为$(1,1)$，总计六对。

再次注意，如果被移除元素的索引集合不同，即使子序列内容相同，我们也视为不同的子序列。

样例输入3

4 4

3 4 5 6

3 4 5 6

样例输出3

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

样例输入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

样例输出5

846527861

请确保输出结果对$10^9+7$取模。