← 返回题目列表

AtCoder · abc130_e

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 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.