Cho dãy gồm N số nguyên ~a1, a2, …, aN~. Người ta gọi một đoạn gồm các phần tử liên tiếp bất kỳ trong dãy ban đầu là đoạn con. Hai đoạn con là khác nhau nếu tồn tại ít nhất một phần tử không thuộc cà hai đoạn. Ví dụ dãy: ~(a1, a2, a3, a4)~ thì có các đoạn con là: ~(a1),~ ~(a2),~ ~(a3),~ ~(a4),~ ~(a1, a2),~ ~(a1, a3),~ ~(a1, a4),~ ~(a2, a3),~ ~(a2, a4),~ ~(a3, a4),~ ~(a1, a2, a3),~ ~(a1, a2, a4),~ ~(a1, a3, a4),~ ~(a1, a2, a3, a4)~.

Hãy đếm số đoạn con mà tổng các lũy thừa bậc ~M~ của các phần tử trong đoạn đó chia hết cho ~K~.

Dữ liệu:

Vào từ file DOANCON.INP gồm hai dòng:

• Dòng đầu tiên chứa ba số nguyên dương ~N, M, K (1 \leq N \leq 10^5; 1 \leq M \leq 10^{18}, 1 \leq K \leq 10^5)~;
• Dòng thứ hai chứa ~N~ số tự nhiên ~a1, a2, …, aN (1 \leq ai \leq 10^5)~.

Kết quả:

Ghi ra file DOANCON.OUT số đoạn con mà tổng các lũy thừa bậc ~M~ của các phần tử chia hết cho ~K~.

Ví dụ:

DOANCON.INP

4 1 3
3 2 1 5

DOANCON.OUT

4

DOANCON.INP

4 2 3
3 2 1 5

DOANCON.OUT

3

Giải thích:

Ví dụ 1: bốn đoạn con là (3), (2,1), (3, 2, 1) và (1, 5)

Ví dụ 2: ba đoạn con đó là (3), (2, 1, 5), (3, 2, 1, 5)

Ràng buộc:

• Subtask1: 45% test ~M = 1, N <= 10^3, a_i <= 10^6~.

• Subtask2: 20% test ~M = 1000, N <= 10^5, a_i <= 10^9~.

• Subtask3: 35% test ~M <= 10^{18}, N <= 10^5, 10^3 <= a_i <= 10^9~.

•