慶熙大學演算法社團 KHUA 為了效仿競技程式設計界在慶祝或紀念時互贈數列作為禮物的文化，決定將數列作為禮物分發給新進成員。然而，每次都創造新的數列太過麻煩，因此他們決定先建立一個數列，並透過循環利用它來產生新的數列。

他們建立了一個無限長的週期數列 $A_1, A_2, \ldots$。$A$ 的前 $N$ 個元素由 $A_1, A_2, \ldots, A_{N}$ 給定，且當 $i > N$ 時，$A_i = A_{i - N}$。該數列的每個元素皆為 $0$ 以上 $M-1$ 以下的整數。對於 $1$ 以上 $N$ 以下的整數 $i$ 以及 $0$ 以上 $M-1$ 以下的整數 $j$，他們希望將定義如下、長度為 $T$ $(T \leq N)$ 的數列 $B^{i, j}_1, B^{i, j}_2, \ldots, B^{i, j}_{T}$ 作為禮物分發：

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

然而，若以此方式產生的數列出現重複，人們可能會發現數列是被循環利用的，因此他們希望盡量避免這種情況。

為了預測數列能被循環利用的程度，需要計算任意兩個循環利用產生的數列相等的機率。假設我們以均勻機率隨機選取整數 $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$），請計算 $B^{i_1, j_1}$ 與 $B^{i_2, j_2}$ 相等的機率。由於每個數值皆為獨立選取，因此 $(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

輸出

180555557

範例 2

輸入

3 1
0 0 0
2

輸出

1

範例 3

輸入

5 10
1 1 2 3 5
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

輸出

724489801

說明

第一個範例的機率為 $13/72$。

在第二個範例中，由於可選擇的數列只有 $(0, 0)$ 一種，因此兩個數列相等的機率為 $1$。

第三個範例的機率為 $1/50$，僅在 $(i_1, j_1) = (i_2, j_2)$ 的情況下兩個數列相等。