Sequence Removal and Pattern Occurrence Sum

Given two integer sequences A and B of lengths \( n \) and \( m \) respectively, and two constants \( W \) and \( d \), where every element of both sequences is in the range \( [1,W] \) (the sequences are 1-indexed). There are \( \binom{W}{d} \) ways to choose \( d \) distinct integers from \( [1,W] \).

For each selection \( S \) (a set of \( d \) integers), remove from sequence A all elements whose values belong to \( S \) (note that no removal is done on B). In the resulting sequence \( A' \) the occurrences of B as a contiguous block are counted. Here an occurrence means that there exists a sequence of indices \( i_1 < i_2 < \cdots < i_m \) such that:

• \( A_{i_k} = B_k \) for \( 1 \le k \le m \), and
• for each adjacent pair \( (i_k, i_{k+1}) \), every index \( r \) satisfying \( i_k < r < i_{k+1} \) is removed (i.e. its value belongs to \( S \)).

The weight of a selection \( S \) is defined as the number of contiguous occurrences of B in \( A' \). Compute the sum over all \( \binom{W}{d} \) selections of their weights, modulo \( 10^9+7 \).

Note: In an occurrence the elements of B (which equal the matched values in A) must remain in \( A' \); consequently, if any element in a gap (between successive matched indices) equals an element of B, that occurrence is invalid.

For example, assume an occurrence is determined by indices \( i_1, i_2, \dots, i_m \) with \( A_{i_k}=B_k \). Let \( G \) be the set of distinct numbers appearing in the gaps between these indices (i.e. between \( i_k+1 \) and \( i_{k+1}-1 \) for every \( k \)). Then the occurrence is valid only if \( G \cap \{B_1, B_2, \dots, B_m\} = \emptyset \). Once this is satisfied, the selection \( S \) must contain every number in \( G \) (so that the gap is removed) and must not contain any number from \( \{B_1, B_2, \dots, B_m\} \). Hence, the number of ways to choose the remainder of \( S \) is

\( \displaystyle \binom{(W - |\{B_1,\dots,B_m\}|) - |G|}{d - |G|} \)

Summing over all valid occurrences yields the final answer.

inputFormat

The first line contains four integers: \( n \), \( m \), \( W \), and \( d \).

The second line contains \( n \) integers representing the sequence A.

The third line contains \( m \) integers representing the sequence B.

outputFormat

Output a single integer: the sum of the weights for all selection schemes, modulo \( 10^9+7 \).

sample

5 2 5 1
1 2 3 2 1
1 2

3