← 返回题目列表

AtCoder · awc0028_e

E. 计算子序列

中文机器翻译题面 查看原题

分数: 433 分

问题陈述

高桥正在研究与序列相关的算法。今天,他正在研究序列中的子序列匹配问题。

给你一个序列 A = (A_1, A_2, \ldots, A_N) 长度 N 和模式序列 P = (P_1, P_2, \ldots, P_K) 长度 K。序列的每个元素 A 和模式序列 P 是正整数。

高桥想找出有多少种选择方法 K 与序列不同的位置 A 使得由这些位置形成的子序列保留原始顺序,与模式序列匹配 P.

更准确地说,找到索引元组的数量 (i_1, i_2, \ldots, i_K) 满意 1 \leq i_1 < i_2 < \cdots < i_K \leq N 这样 A_{i_j} = P_j 适用于所有 j (1 \leq j \leq K).

请注意,如果所选索引元组即使在一个位置上不同,它们也将被视为不同的选择,即使所有所选元素的值都相同。

由于答案可能非常大,请对它求模 10^9 + 7.

约束

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 100
  • K \leq N
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq K)
  • 所有输入均为整数

输入

N K
A_1 A_2 \ldots A_N
P_1 P_2 \ldots P_K
  • 第一行包含两个整数 N 和 K,用空格分隔,表示序列的长度 A 和模式序列的长度 P。
  • 第二行包含元素 序列的 A_1, A_2, \ldots, A_N 序列的 A,以空格分隔。
  • 第三行包含元素 模式序列的 P_1, P_2, \ldots, P_K 模式序列的 P,以空格分隔。

输出

在单行上打印满足条件的索引元组的数量,模 10^9 + 7.


示例输入 1

5 2
1 2 1 2 1
1 2

示例输出 1

3

示例输入 2

8 3
3 1 4 1 5 9 2 6
1 5 6

示例输出 2

2

示例输入 3

15 4
2 3 2 3 2 3 2 3 2 3 2 3 2 3 2
2 3 2 3

示例输出 3

126