慶熙大学校のアルゴリズムサークルKHUAでは、お祝い事や記念日がある際に数列をプレゼントとして贈り合うというPS界の文化に倣い、新入部員に数列をプレゼントすることにした。しかし、毎回新しい数列を作成するのは面倒であるため、一つの数列を作成し、それを再利用して新しい数列を作ることにした。

再利用する無限の長さの周期数列 $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$$

しかし、このように作成された数列が重複すると、人々は数列が再利用されていることに気づいてしまうため、このような状況は可能な限り避けたいと考えている。

再利用して作成した任意の二つの数列が等しくなる確率を求め、どれくらい数列を再利用できるかを予測しようとしている。$1 \leq i_1, i_2 \leq N$ かつ $0 \leq j_1, j_2 \leq M-1$ である整数 $i_1, i_2, j_1, j_2$ を一様な確率でランダムに選んだとき、$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}$ は $10^9 + 7$ を法とする $Q$ のモジュラ逆数である。

入出力例

入出力例 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)$ である場合にのみ二つの数列が等しくなる。