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

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

Dữ liệu vào:

+ Dòng đầu ghi 3 số tự nhiên \(n,\ m,\ k\) 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 \leq n \leq 10^{5};1 \leq m \leq 10^{18};1 \leq k \leq 10^{5})\).

Dòng tiếp theo ghi \(n\) số tự nhiên \(a_{1},a_{2},\ldots a_{n}\) (các số đều không vượt quá \(10^{50},\) hay là: \(0 \leq a_{i} \leq 10^{50}\) với mọi \(i\) )

Kết quả:

+ 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ụ:

Ràng buộc:

- Có 45% test chấm bài có \(m = 1,\ \ n \leq 10^{3},a_{i} \leq 10^{6};\)

- Có 30% test chấm bài có \(m \leq 1000\), \(n \leq 10^{5},a_{i} \leq 10^{9};\)

- Có 25% test chấm bài có \(10^{9} \leq m \leq 10^{18},\ n \leq 10^{5},10^{30} \leq a_{i} \leq 10^{50}.\)