В алгоритмическом клубе KHUA университета Кёнхи, следуя культуре PS-сообщества, где принято дарить друг другу последовательности чисел по случаю праздников или памятных дат, решили дарить последовательности новым участникам. Однако, поскольку придумывать каждый раз новую последовательность утомительно, было решено создать одну базовую последовательность и использовать её для генерации новых.

Создается периодическая последовательность бесконечной длины $A_1, A_2, \ldots$. Первые $N$ элементов $A$ задаются как $A_1, A_2, \ldots, A_{N}$, а для $i > N$ выполняется $A_i = A_{i - N}$. Каждый элемент этой последовательности является целым числом от $0$ до $M-1$. Для целого числа $i$ ($1 \leq i \leq N$) и целого числа $j$ ($0 \leq j \leq M-1$) мы хотим дарить последовательность $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ длины $T$ ($T \leq N$), определяемую следующим образом:

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

Однако, если созданные таким образом последовательности будут повторяться, люди могут заметить, что последовательности переиспользуются, поэтому мы стараемся избегать таких ситуаций.

Мы хотим предсказать, насколько часто можно переиспользовать последовательности, вычислив вероятность того, что две случайно выбранные последовательности окажутся одинаковыми. Необходимо найти вероятность того, что $B^{i_1, j_1}$ и $B^{i_2, j_2}$ равны, если целые числа $i_1, i_2$ ($1 \leq i_1, i_2 \leq N$) и $j_1, j_2$ ($0 \leq j_1, j_2 \leq M-1$) выбраны случайным образом с равномерным распределением. Поскольку каждое число выбирается независимо, случай $(i_1, j_1) = (i_2, j_2)$ также возможен. Вероятность должна быть вычислена с учетом этого случая.

Входные данные

В первой строке через пробел заданы целые числа $N$ и $M$ ($1 \leq N, M \leq 10^5$).

Во второй строке через пробел заданы $N$ целых чисел $A_1, A_2, \ldots, A_{N}$ ($0 \leq A_i \leq M - 1$).

В третьей строке задано целое число $T$ ($1 \leq T \leq N$).

Выходные данные

Выведите вероятность того, что две сгенерированные последовательности равны. Если искомая вероятность в виде несократимой дроби равна ${P}/{Q}$, выведите $P \times Q^{-1} \bmod 10^9 + 7$, где $Q^{-1}$ — модульная мультипликативная инверсия $Q$ по модулю $10^9 + 7$.

Примеры

Пример 1

6 4
1 2 1 2 3 0
2

Выходные данные 1

180555557

Пример 2

3 1
0 0 0
2

Выходные данные 2

1

Пример 3

5 10
1 1 2 3 5
3

Выходные данные 3

140000001

Пример 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

Выходные данные 4

724489801

Примечание

Вероятность в первом примере равна $13/72$.

Во втором примере существует только одна возможная последовательность $(0, 0)$, поэтому вероятность того, что две последовательности совпадут, равна $1$.

Вероятность в третьем примере равна $1/50$; последовательности равны только в случае $(i_1, j_1) = (i_2, j_2)$.