Cho dãy gồm 𝑁 số tự nhiên: 𝑎1, 𝑎2, … 𝑎𝑁. 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 vào cả hai đoạn. Ví dụ dãy: {𝑎1; 𝑎2; 𝑎3; 𝑎4} thì có mười đoạn con là: {𝑎1}, {𝑎2}, {𝑎3}, {𝑎4}, {𝑎1; 𝑎2}, {𝑎2; 𝑎3}, {𝑎3; 𝑎4}, {𝑎1; 𝑎2; 𝑎3}, {𝑎2; 𝑎3; 𝑎4}, {𝑎1; 𝑎2; 𝑎3; 𝑎4}.

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

Dữ liệu vào: Đọc dữ liệu vào từ tệp bai5.inp

Dòng đầu ghi 3 số tự nhiên 𝑁, 𝑀, 𝐾 tương ứng là số phần tử của dãy ban đầu, số mũ, và số K cần chia hết. (1 ≤ 𝑁 ≤ 10^5; 1 ≤ 𝑀 ≤ 10^18; 1 ≤ 𝐾 ≤ 10^5).

Dòng tiếp theo ghi N số tự nhiên 𝑎1, 𝑎2, … 𝑎𝑁 (các số đều không vượt quá 10^50, hay là: 0 ≤ 𝑎𝑖 ≤ 10^50 với mọi 𝑖)

Dữ liệu ra: Ghi kết quả ra tệp bai5.out

Ghi số đoạn con mà 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ụ:

Input 01:

4 1 3
3 2 1 5

Output 01:

4

Giải thích: Có các đoạn {3},{2;1}, {1;5}; {3;2;1} vì: 3^1 ⋮ 3; (2^1 + 1^1) ⋮ 3; (1^1 + 5^1) ⋮ 3 ; (3^1 + 2^1 + 1^1) ⋮ 3

Input 02:

4 2 3
3 2 1 5

Output 02:

3

Giải thích: Có các đoạn {3}, {2;1;5}, {3;2;1;5} vì: 3^2 ⋮ 3; (2^2 + 1^2 + 5^2) ⋮ 3; (3^2 + 2^2 + 1^2 + 5^2) ⋮ 3

• Có 45% test chấm bài có 𝑀 = 1, 𝑁 ≤ 10^3, 𝑎𝑖 ≤ 10^6;

• Có 30% test chấm bài có 𝑀 ≤ 1000, 𝑁 ≤ 10^5, 𝑎𝑖 ≤ 10^9;

• Có 25% test chấm bài có 10^9 ≤ 𝑀 ≤ 10^18, 𝑁 ≤ 10^5, 10^30 ≤ 𝑎𝑖 ≤ 10^50.