分数: 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 is N.
- 的长度 T is 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.