题目描述

给出两个长度分别为 $N$ 和 $M$ 的整数序列 $S$ 和 $T$，它们均由 $1$ 到 $10^5$（含 $10^5$）之间的整数组成。

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

子序列的说明：

A 的子序列是指通过从 A 删除零个或多个元素而不改变顺序而获得的序列。

对于 $S$ 和 $T$ 而言，如果子序列的内容相同，但是被删除元素的索引集（位置）不同，也当成两个不同的子序列。

输出答案模 $10^9 + 7$ 的结果。

输入格式

第一行输入两个正整数 $N, M$，$1 \le N, M \le 2000$。

第二行输入序列 $S$，总共 $N$ 个数。

第三行输入序列 $T$，总共 $M$ 个数。

$1 \le S_i, T_i \le 10^5$。

输出格式

在 $S$ 子序列和 $T$ 子序列中，子序列的内容相同的个数。

2 2
1 3
3 1

3

2 2
1 1
1 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