Trong thời gian nghỉ hè, bạn B tham gia một trò chơi trực tuyến và được nhận quà.

Để thử thách khả năng của người chơi, hệ thống đưa ra cách nhận quà như sau:

Cho ~N~ món quà có giá trị lần lượt là ~a_1, a_2, \dots, a_N~ và hai số ~X, M~. Người chơi chỉ được nhận dãy các món quà liên tiếp nhau có tổng lũy thừa bậc ~X~ của giá trị các món quà chia hết cho ~M~. Hai dãy quà liên tiếp là khác nhau nếu tồn tại ít nhất một món quà không thuộc cả hai dãy.

Ví dụ với ~3~ món quà: ~\{1, 5, 5\}~ thì có ~6~ dãy các món quà liên tiếp là ~\{1\}~, ~\{5\}~, ~\{5\}~, ~\{1, 5\}~, ~\{5, 5\}~, ~\{1, 5, 5\}~, với ~X = 1~ và ~M = 5~ thì chỉ có ~3~ phương án nhận quà là: ~\{5\}~, ~\{5\}~ và ~\{5, 5\}~.

Yêu cầu: Hãy cho biết bạn B có bao nhiêu phương án nhận quà.

Input

• Dòng thứ nhất chứa ba số nguyên dương ~N, X, M~ ~(1 \le N \le 10^5; 1 \le X \le 10^{18}; 1 \le M \le 10^5)~ lần lượt là số món quà và giá trị ~X, M~ theo yêu cầu.

• Dòng thứ hai chứa ~N~ số tự nhiên ~a_1, a_2, \dots, a_N~ ~(1 \le a_i \le 10^{20})~ lần lượt là giá trị các món quà.

Các số trên cùng dòng cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là kết quả cần tìm.

Scoring

Sample Input 1

3 1 5
1 5 5

Sample Output 1

3

Sample Input 2

5 2 3
3 3 3 3 3

Sample Output 2

15