Cho dãy N số nguyên a_1, a_2, ..., a_N. 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: {a_1, a_2, a_3, a_4} thì có mười đoạn con là: {a_1}, {a_2}, {a_3}, {a_4}, {a_1, a_2}, {a_1, a_2, a_3}, {a_1, a_2, a_3, a_4}, {a_2, a_3}, {a_2, a_3, a_4}, {a_3, a_4}.

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

- Dòng đầu chứa ba số nguyên dương N, M, K (1 <= N <= 10^5; 1 <= M <= 10^18, 1 <= K <= 10^5).
- Dòng thứ hai chứa N số tự nhiên a_1, a_2, ..., a_N (1 <= a_i <= 10^50).

Kết quả

Ghi ra một số nguyên duy nhất là số đoạn con có 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ụ 1

4 1 3
3 2 1 5

4

Ví dụ 2

4 2 3
3 2 1 5

3

Ràng buộc

• Subtask 1: Có 45% số test M = 1, N <= 10^3, a_i <= 10^6.
  
• Subtask 2: Có 20% số test M <= 1000, N <= 10^5, a_i <= 10^9.
  
• Subtask 3: Có 35% số test M <= 10^18, N <= 10^5, 10^30 <= a_i <= 10^50.