题目描述

给定两个整数序列 $S$ 和 $T$，长度分别为 $N$ 和 $M$，均由介于 1 和 $10^5$(含)之间的整数组成。

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

这里所说的子序列是指通过从原序列中移除零个或多个元素，并按原顺序连接剩余元素所得到的序列。

对于 $S$ 和 $T$，即使两个子序列的内容相同，如果移除元素的索引集合不同，我们也认为这两个子序列是不同的。

由于答案可能非常大，因此请输出对 $10^9+7$取模后的结果。

输入

第一行两个整数表示两个序列的长度$N,M$

第二行一个长度为$N$的序列

第三行一个长度为$M$的序列

输出

打印满足条件的 $S$和 $T$的子序列对数，对 $10^9+7$取模后的结果。

2 2
1 3
3 1

3

样例解释

$S$ 有四个子序列:(),(1),(3),(1,3)

$T$ 也有四个子序列:(),(3),(1),(3,1)。

有1x1对子序列，其中两个子序列都是()

有1x1对子序列，其中两个子序列都是(1)

也有 1 x1对子序列，其中两个子序列都是(3)，总计三对。

2 2
1 1
1 1

6

样例解释

$S$ 有四个子序列:(),(1),(1),(1,1)。

$T$ 也有四个子序列:(),(1),(1),(1,1)。

有1x1对子序列，其中两个子序列都是()，

有 2 x2对子序列，其中两个子序列都是(1)，

以及有1x1对子序列，其中两个子序列都是(1,1)，总计六对。

请注意，即使两个子序列的内容相同，如果移除元素的索引集合不同，我们也认为这两个子序列是不同的。

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

提示

$1 \leq N,M \leq 2 \times 10^3$

$1 \leq S_i,T_i \leq 10^5$