En el club de algoritmos KHUA de la Universidad de Kyung Hee, siguiendo la cultura del mundo de la programación competitiva de intercambiar secuencias como regalo en ocasiones especiales o conmemorativas, han decidido regalar secuencias a los nuevos miembros. Sin embargo, como crear una secuencia nueva cada vez resulta tedioso, han decidido crear una secuencia base y reutilizarla para generar nuevas secuencias.

Se crea una secuencia periódica de longitud infinita $A_1, A_2, \ldots$. Los primeros $N$ elementos de $A$ se dan como $A_1, A_2, \ldots, A_{N}$, y para $i > N$, se cumple que $A_i = A_{i - N}$. Cada elemento de esta secuencia es un número entero entre $0$ y $M-1$. Para un entero $i$ tal que $1 \leq i \leq N$ y un entero $j$ tal que $0 \leq j \leq M-1$, se desea regalar una secuencia $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ de longitud $T$ $(T \leq N)$, definida de la siguiente manera:

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

No obstante, si las secuencias generadas de esta manera se repiten, la gente podría darse cuenta de que se están reutilizando, por lo que se intenta evitar esta situación tanto como sea posible.

Para predecir cuánto se pueden reutilizar las secuencias, se debe calcular la probabilidad de que dos secuencias elegidas al azar sean iguales. Se deben elegir enteros $i_1, i_2$ tales que $1 \leq i_1, i_2 \leq N$ y enteros $j_1, j_2$ tales que $0 \leq j_1, j_2 \leq M-1$ con probabilidad uniforme, y calcular la probabilidad de que $B^{i_1, j_1}$ y $B^{i_2, j_2}$ sean iguales. Dado que cada número se elige de forma independiente, el caso $(i_1, j_1) = (i_2, j_2)$ también puede ocurrir. La probabilidad debe calcularse incluyendo este caso.

Entrada

La primera línea contiene los enteros $N$ y $M$ separados por un espacio ($1 \leq N, M \leq 10^5$).

La segunda línea contiene $N$ enteros $A_1, A_2, \ldots, A_{N}$ separados por espacios ($0 \leq A_i \leq M - 1$).

La tercera línea contiene el entero $T$ ($1 \leq T \leq N$).

Salida

Imprima la probabilidad de que las dos secuencias generadas por reutilización sean iguales. Si la probabilidad expresada como una fracción irreducible es ${P}/{Q}$, imprima $P \times Q^{-1} \bmod 10^9 + 7$ en su lugar. Aquí, $Q^{-1}$ es el inverso multiplicativo modular de $Q$ respecto a $10^9 + 7$.

Ejemplos

Entrada 1

6 4
1 2 1 2 3 0
2

Salida 1

180555557

Entrada 2

3 1
0 0 0
2

Salida 2

1

Entrada 3

5 10
1 1 2 3 5
3

Salida 3

140000001

Entrada 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

Salida 4

724489801

Nota

La probabilidad del primer ejemplo es $13/72$.

En el segundo ejemplo, solo existe una secuencia posible $(0, 0)$, por lo que la probabilidad de que las dos secuencias sean iguales es $1$.

La probabilidad del tercer ejemplo es $1/50$, donde las secuencias son iguales solo en el caso en que $(i_1, j_1) = (i_2, j_2)$.