Trong một buổi giao lưu văn nghệ gồm ~n~ bạn học sinh, mỗi tiết mục văn nghệ sẽ do đúng ba bạn thực hiện. Bạn thứ ~i~ có mức độ vui vẻ là số nguyên dương ~h_i (i=1, 2,..., n)~. Khi đó, nếu bộ ba bạn ~i, j, k (1 \le i \lt j \lt k \le n)~ thực hiện tiết mục văn nghệ sẽ tạo ra độ vui vẻ là ~h_i \times h_j \times h_k~. Ban tổ chức muốn tính tổng độ vui vẻ nếu mỗi bộ ba bạn sẽ tham gia thực hiện đúng một tiết mục văn nghệ.

Yêu cầu: Cho ~n~ số nguyên dương ~h_1, h_2,..., h_n~ là mức độ vui vẻ của ~n~ bạn học sinh và số nguyên dương ~M~, gọi ~S~ tổng độ vui vẻ, hãy tính phần dư trong phép chia ~S~ cho ~M~.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên dương ~n, M (M \le 10^{12})~;
• Dòng thứ hai chứa n số nguyên dương ~h_1, h_2,..., h_n~ là mức độ vui vẻ của n thí sinh.

Kết quả:

• Ghi ra một số nguyên duy nhất là giá trị yêu cầu cần tính.

Ràng buộc:

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài có ~n = 3, h_i \le 10^3~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài có ~n \le 300, h_i \le 10^6~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài có ~n \le 3000, h_i \le 10^6~;
• Có ~20\%~ số test khác ứng với ~20\%~ số điểm của bài có ~n \le 10^5, h_i \le 10^6~;
• Có ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài có có ~n \le 10^5, h_i \le 10^{12}~.

Ví dụ:

Sample Input 1

3 5
1 3 2

Sample Output 1

1

Sample Input 2

4 5
1 1 1 1

Sample Output 2

4