题目描述

You are given two integer sequences $S$ and $T$ of length $N$ and $M$, respectively, both consisting of integers between $1$ and $10^5$ (inclusive).

In how many pairs of a subsequence of $S$ and a subsequence of $T$ do the two subsequences are the same in content?

Here the subsequence of $A$ is a sequence obtained by removing zero or more elements from $A$ and concatenating the remaining elements without changing the order.

For both $S$ and $T$, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.

Since the answer can be tremendous, print the number mod $10^9+7$.

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

在 $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$ 的子序列的对数。

样例 #1

样例输入 #1

2 2
1 3
3 1

样例输出 #1

3

样例 #2

样例输入 #2

2 2
1 1
1 1

样例输出 #2

6

样例 #3

样例输入 #3

4 4
3 4 5 6
3 4 5 6

样例输出 #3

16

样例 #4

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

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

说明

数据规模与约定

• $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 \times 1$ 对子序列中的子序列都是 $(1)$ ， $1 \times 1$ 对子序列中的子序列都是 $(3)$ ，总共有三对子序列。

样例 $2$ 解释

$S$ 有四个子序列： $(), (1), (1), (1, 1)$ .

$T$ 有四个子序列： $(), (1), (1), (1, 1)$ .

还有 $1 \times 1$ 对子序列中的子序列都是 $()$ ， $2 \times 2$ 对子序列中的子序列都是 $(1)$ ， $1 \times 1$ 对子序列中的子序列都是 $(1,1)$ ，总共六对子序列。请再次注意，如果被删除元素的索引集不同，即使子序列的内容相同，我们也要区分两个子序列。

样例 $5$ 解释

请务必打印出 $10^9+7$ 的模数。