경희대학교 알고리즘 동아리 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)$인 경우도 발생할 수 있다. 이 경우를 포함하여 확률을 구해야 한다.

Input

첫 줄에 정수 $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$)

Output

재활용해서 만든 두 수열이 같을 확률을 출력하라. 구한 확률이 기약분수로 나타냈을 때 ${P}/{Q}$라면 $P \times Q^{-1} \bmod 10^9 + 7$를 대신 출력하라. 여기서 $Q^{-1}$은 $10^9 + 7$에 대한 $Q$의 모듈러 역원이다.

Examples

Input 1

6 4
1 2 1 2 3 0
2

Output 1

180555557

Input 2

3 1
0 0 0
2

Output 2

1

Input 3

5 10
1 1 2 3 5
3

Output 3

140000001

Input 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

Output 4

724489801

Note

첫 번째 예제의 확률은 $13/72$이다.

두 번째 예제에서는 선택할 수 있는 수열이 $(0, 0)$ 하나밖에 없으므로 두 수열이 같을 확률은 $1$이다.

세 번째 예제의 확률은 $1/50$으로, $(i_1, j_1) = (i_2, j_2)$인 경우에만 두 수열이 같다.