Le club d'algorithmique de l'Université Kyung Hee, KHUA, souhaite offrir des suites de nombres à ses nouveaux membres en cadeau, en s'inspirant de la culture de la communauté PS où l'on s'échange des suites pour célébrer des événements. Cependant, comme il est fastidieux de créer une nouvelle suite à chaque fois, ils ont décidé de créer une suite de base et de la recycler pour en générer de nouvelles.

Ils créent une suite périodique de longueur infinie $A_1, A_2, \ldots$. Les $N$ premiers éléments de $A$ sont donnés par $A_1, A_2, \ldots, A_{N}$, et pour $i > N$, on a $A_i = A_{i - N}$. Chaque élément de cette suite est un entier compris entre $0$ et $M-1$ inclus. Pour tout entier $i$ tel que $1 \leq i \leq N$ et tout entier $j$ tel que $0 \leq j \leq M-1$, ils ont pensé qu'il serait agréable d'offrir une suite $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ de longueur $T$ ($T \leq N$), définie comme suit :

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

Cependant, si les suites ainsi créées sont identiques, les gens pourraient se rendre compte qu'ils recyclent les suites, ils essaient donc d'éviter cette situation autant que possible.

Ils souhaitent prédire dans quelle mesure ils peuvent recycler les suites en calculant la probabilité que deux suites choisies au hasard soient identiques. Vous devez calculer la probabilité que $B^{i_1, j_1}$ et $B^{i_2, j_2}$ soient identiques lorsque $i_1, i_2, j_1, j_2$ sont choisis uniformément et indépendamment parmi les entiers tels que $1 \leq i_1, i_2 \leq N$ et $0 \leq j_1, j_2 \leq M-1$. Comme chaque nombre est choisi indépendamment, le cas $(i_1, j_1) = (i_2, j_2)$ peut également se produire. La probabilité doit inclure ce cas.

Entrée

La première ligne contient deux entiers $N$ et $M$ séparés par un espace ($1 \leq N, M \leq 10^5$).

La deuxième ligne contient $N$ entiers $A_1, A_2, \ldots, A_{N}$ séparés par un espace ($0 \leq A_i \leq M - 1$).

La troisième ligne contient un entier $T$ ($1 \leq T \leq N$).

Sortie

Affichez la probabilité que deux suites créées par recyclage soient identiques. Si la probabilité obtenue, exprimée sous forme de fraction irréductible, est ${P}/{Q}$, affichez $P \times Q^{-1} \bmod 10^9 + 7$ à la place. Ici, $Q^{-1}$ est l'inverse modulaire de $Q$ modulo $10^9 + 7$.

Exemples

Entrée 1

6 4
1 2 1 2 3 0
2

Sortie 1

180555557

Remarque

La probabilité du premier exemple est $13/72$.

Entrée 2

3 1
0 0 0
2

Sortie 2

1

Remarque

Dans le deuxième exemple, il n'y a qu'une seule suite possible $(0, 0)$, donc la probabilité que deux suites soient identiques est $1$.

Entrée 3

5 10
1 1 2 3 5
3

Sortie 3

140000001

Remarque

La probabilité du troisième exemple est $1/50$, où les deux suites ne sont identiques que dans le cas $(i_1, j_1) = (i_2, j_2)$.

Entrée 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

Sortie 4

724489801