庆熙大学算法社团 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}$ 是 $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)$ 的情况下两个数列相等。