Câu lạc bộ thuật toán KHUA tại Đại học Kyung Hee muốn tặng các dãy số cho các thành viên mới, noi theo văn hóa của giới PS (Problem Solving) là trao đổi các dãy số làm quà tặng trong những dịp kỷ niệm. Tuy nhiên, vì việc tạo ra dãy số mới mỗi lần rất phiền phức, họ quyết định tạo ra một dãy số và tái sử dụng nó để tạo ra các dãy số mới.

Họ tạo ra một dãy số tuần hoàn vô hạn $A_1, A_2, \ldots$. $N$ phần tử đầu tiên của $A$ được cho là $A_1, A_2, \ldots, A_{N}$, và với $i > N$ thì $A_i = A_{i - N}$. Mỗi phần tử của dãy số này là một số nguyên từ $0$ đến $M-1$. Với mỗi số nguyên $i$ thỏa mãn $1 \leq i \leq N$ và số nguyên $j$ thỏa mãn $0 \leq j \leq M-1$, họ muốn tặng một dãy số có độ dài $T$ $(T \leq N)$ được định nghĩa như sau:

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

Tuy nhiên, nếu các dãy số được tạo ra theo cách này bị trùng lặp, mọi người có thể nhận ra rằng các dãy số đang được tái sử dụng, vì vậy họ muốn tránh tình trạng này nhiều nhất có thể.

Họ muốn dự đoán khả năng tái sử dụng dãy số bằng cách tính xác suất để hai dãy số bất kỳ được tạo ra từ việc tái sử dụng là giống nhau. Bạn cần tính xác suất để $B^{i_1, j_1}$ và $B^{i_2, j_2}$ bằng nhau khi chọn ngẫu nhiên các số nguyên $i_1, i_2$ ($1 \leq i_1, i_2 \leq N$) và $j_1, j_2$ ($0 \leq j_1, j_2 \leq M-1$) với xác suất đồng nhất. Vì mỗi số được chọn độc lập, trường hợp $(i_1, j_1) = (i_2, j_2)$ cũng có thể xảy ra. Xác suất cần tính phải bao gồm cả trường hợp này.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ cách nhau bởi dấu cách ($1 \leq N, M \leq 10^5$).

Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \ldots, A_{N}$ cách nhau bởi dấu cách ($0 \leq A_i \leq M - 1$).

Dòng thứ ba chứa số nguyên $T$ ($1 \leq T \leq N$).

Dữ liệu ra

In ra xác suất để hai dãy số được tạo ra từ việc tái sử dụng là giống nhau. Nếu xác suất tìm được dưới dạng phân số tối giản là ${P}/{Q}$, hãy in ra $P \times Q^{-1} \bmod 10^9 + 7$. Trong đó $Q^{-1}$ là nghịch đảo mô-đun của $Q$ theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

6 4
1 2 1 2 3 0
2

Dữ liệu ra 1

180555557

Ghi chú

Xác suất trong ví dụ đầu tiên là $13/72$.

Dữ liệu vào 2

3 1
0 0 0
2

Dữ liệu ra 2

1

Ghi chú

Trong ví dụ thứ hai, chỉ có một dãy số duy nhất có thể chọn là $(0, 0)$, nên xác suất để hai dãy số giống nhau là $1$.

Dữ liệu vào 3

5 10
1 1 2 3 5
3

Dữ liệu ra 3

140000001

Ghi chú

Xác suất trong ví dụ thứ ba là $1/50$, trong đó hai dãy số chỉ bằng nhau khi $(i_1, j_1) = (i_2, j_2)$.

Dữ liệu vào 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

Dữ liệu ra 4

724489801