分数: 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