Koło algorytmiczne KHUA na Uniwersytecie Kyung Hee, wzorując się na kulturze PS (Problem Solving), w której prezenty wymienia się w formie ciągów liczbowych, postanowiło obdarować nowych członków ciągami. Ponieważ tworzenie za każdym razem nowego ciągu jest uciążliwe, postanowiono stworzyć jeden ciąg i wykorzystywać go ponownie do generowania nowych.

Tworzymy nieskończony ciąg okresowy $A_1, A_2, \ldots$. Pierwsze $N$ elementów ciągu $A$ jest danych jako $A_1, A_2, \ldots, A_{N}$, a dla $i > N$ zachodzi $A_i = A_{i - N}$. Każdy element tego ciągu jest liczbą całkowitą z przedziału od $0$ do $M-1$. Dla liczby całkowitej $i$ z przedziału $1 \leq i \leq N$ oraz liczby całkowitej $j$ z przedziału $0 \leq j \leq M-1$, zdefiniowano ciąg $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ o długości $T$ $(T \leq N)$, który ma zostać wręczony jako prezent:

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

Jednakże, jeśli tak utworzone ciągi będą się powtarzać, ludzie mogą zorientować się, że ciągi są wykorzystywane ponownie, dlatego staramy się unikać takiej sytuacji.

Chcemy przewidzieć, jak bardzo można ponownie wykorzystywać ciągi, obliczając prawdopodobieństwo, że dwa losowo wybrane ciągi będą identyczne. Należy obliczyć prawdopodobieństwo, że $B^{i_1, j_1}$ i $B^{i_2, j_2}$ są sobie równe, gdy liczby całkowite $i_1, i_2$ ($1 \leq i_1, i_2 \leq N$) oraz $j_1, j_2$ ($0 \leq j_1, j_2 \leq M-1$) są wybierane z jednostajnym rozkładem prawdopodobieństwa. Ponieważ każda liczba jest wybierana niezależnie, może wystąpić przypadek $(i_1, j_1) = (i_2, j_2)$. Prawdopodobieństwo należy obliczyć, uwzględniając również ten przypadek.

Wejście

W pierwszej linii podano liczby całkowite $N$ i $M$ oddzielone spacją ($1 \leq N, M \leq 10^5$).

W drugiej linii podano $N$ liczb całkowitych $A_1, A_2, \ldots, A_{N}$ oddzielonych spacją ($0 \leq A_i \leq M - 1$).

W trzeciej linii podano liczbę całkowitą $T$ ($1 \leq T \leq N$).

Wyjście

Wypisz prawdopodobieństwo, że dwa wygenerowane ciągi są identyczne. Jeśli prawdopodobieństwo w postaci ułamka nieskracalnego wynosi ${P}/{Q}$, wypisz $P \times Q^{-1} \bmod 10^9 + 7$. Tutaj $Q^{-1}$ jest odwrotnością modularną $Q$ względem $10^9 + 7$.

Przykład

Przykład 1

6 4
1 2 1 2 3 0
2

Wyjście 1

180555557

Przykład 2

3 1
0 0 0
2

Wyjście 2

1

Przykład 3

5 10
1 1 2 3 5
3

Wyjście 3

140000001

Przykład 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

Wyjście 4

724489801

Uwagi

Prawdopodobieństwo w pierwszym przykładzie wynosi $13/72$.

W drugim przykładzie istnieje tylko jeden możliwy ciąg $(0, 0)$, więc prawdopodobieństwo, że dwa ciągi będą takie same, wynosi $1$.

Prawdopodobieństwo w trzecim przykładzie wynosi $1/50$, gdzie ciągi są identyczne tylko w przypadku $(i_1, j_1) = (i_2, j_2)$.