/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 433 点
問題文
高橋君は数列に関するアルゴリズムの研究をしています。今日は、数列における部分列（subsequence）のマッチングの問題に取り組んでいます。
長さ N の数列 A = (A_1, A_2, \ldots, A_N) と、長さ K のパターン数列 P = (P_1, P_2, \ldots, P_K) が与えられます。数列 A およびパターン数列 P の各要素はいずれも正の整数です。
高橋君は、数列 A の中から異なる K 個の位置を選び、それらを元の順序を保ったまま並べた数列がパターン数列 P と一致するような選び方が何通りあるかを求めたいと思っています。
より正確には、1 \leq i_1 < i_2 < \cdots < i_K \leq N を満たす添字の組 (i_1, i_2, \ldots, i_K) であって、すべての j (1 \leq j \leq K) に対して A_{i_j} = P_j となるものの個数を求めてください。
ここで、選んだ添字の組が 1 つでも異なれば、たとえ選ばれた要素の値がすべて同じであっても、異なる選び方として数えることに注意してください。
答えは非常に大きくなる可能性があるため、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
- 1 行目には、数列 A の長さを表す整数 N と、パターン数列 P の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列 A の要素 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 3 行目には、パターン数列 P の要素 P_1, P_2, \ldots, P_K が、スペース区切りで与えられる。
出力
条件を満たす添字の組の個数を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 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
Score : 433 pts
Problem Statement
Takahashi is researching algorithms related to sequences. Today, he is working on a subsequence matching problem in sequences.
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N and a pattern sequence P = (P_1, P_2, \ldots, P_K) of length K. Each element of the sequence A and the pattern sequence P is a positive integer.
Takahashi wants to find the number of ways to choose K distinct positions from the sequence A such that the subsequence formed by those positions, preserving the original order, matches the pattern sequence P.
More precisely, find the number of index tuples (i_1, i_2, \ldots, i_K) satisfying 1 \leq i_1 < i_2 < \cdots < i_K \leq N such that A_{i_j} = P_j holds for all j (1 \leq j \leq K).
Note that if the chosen index tuples differ in even one position, they are counted as distinct selections, even if the values of all selected elements are the same.
Since the answer can be very large, find it modulo 10^9 + 7.
Constraints
- 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)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N P_1 P_2 \ldots P_K
- The first line contains two integers N and K, separated by a space, representing the length of the sequence A and the length of the pattern sequence P, respectively.
- The second line contains the elements A_1, A_2, \ldots, A_N of the sequence A, separated by spaces.
- The third line contains the elements P_1, P_2, \ldots, P_K of the pattern sequence P, separated by spaces.
Output
Print on a single line the number of index tuples satisfying the condition, modulo 10^9 + 7.
Sample Input 1
5 2 1 2 1 2 1 1 2
Sample Output 1
3
Sample Input 2
8 3 3 1 4 1 5 9 2 6 1 5 6
Sample Output 2
2
Sample Input 3
15 4 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 2 3 2 3
Sample Output 3
126