The algorithm club KHUA at Kyung Hee University, following the PS community's culture of exchanging sequences as gifts for celebrations or commemorative events, intends to distribute sequences to new members. However, since creating new sequences every time is tedious, they decided to create one sequence and recycle it to generate new ones.

They create an infinite periodic sequence $A_1, A_2, \ldots$. The first $N$ elements of $A$ are given as $A_1, A_2, \ldots, A_{N}$, and for $i > N$, $A_i = A_{i - N}$. Each element of this sequence is an integer between $0$ and $M-1$ inclusive. They thought it would be nice to distribute as gifts sequences $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ of length $T$ ($T \leq N$), defined for an integer $i$ ($1 \leq i \leq N$) and an integer $j$ ($0 \leq j \leq M-1$) as follows:

$$B^{i, j}_k = (A_{i + k} + j)\;mod\,M$$

However, they want to avoid this situation as much as possible because if the generated sequences are identical, people might notice that the sequences are being recycled.

They want to predict how much the sequences can be recycled by calculating the probability that two randomly generated sequences are identical. You need to find the probability that $B^{i_1, j_1}$ and $B^{i_2, j_2}$ are equal when $i_1, i_2, j_1, j_2$ are chosen uniformly at random, where $1 \leq i_1, i_2 \leq N$ and $0 \leq j_1, j_2 \leq M-1$. Since each number is chosen independently, the case $(i_1, j_1) = (i_2, j_2)$ can also occur. The probability must be calculated including this case.

Input

The first line contains two integers $N$ and $M$ separated by a space ($1 \leq N, M \leq 10^5$).

The second line contains $N$ integers $A_1, A_2, \ldots, A_{N}$ separated by spaces ($0 \leq A_i \leq M - 1$).

The third line contains an integer $T$ ($1 \leq T \leq N$).

Output

Output the probability that two recycled sequences are identical. If the probability expressed as an irreducible fraction is ${P}/{Q}$, output $P \times Q^{-1} \bmod 10^9 + 7$ instead. Here, $Q^{-1}$ is the modular multiplicative inverse of $Q$ modulo $10^9 + 7$.

Examples

Input 1

6 4
1 2 1 2 3 0
2

Output 1

180555557

Input 2

3 1
0 0 0
2

Output 2

1

Input 3

5 10
1 1 2 3 5
3

Output 3

140000001

Input 4

28 12
0 3 1 2 3 1 2 1 2 5 8 6 7 8 6 7 6 7 10 1 11 0 1 11 0 11 0 3
3

Output 4

724489801

Note

The probability for the first example is $13/72$.

In the second example, there is only one possible sequence $(0, 0)$, so the probability that two sequences are identical is $1$.

The probability for the third example is $1/50$, where the two sequences are identical only when $(i_1, j_1) = (i_2, j_2)$.