Bạn được cho một dãy gồm N số nguyên ~(1 ≤ N≤ 10^5)~ và một số nguyên K ~(1 ≤ K≤ 10^1~~^8)~

Yêu cầu:Đếm đoạn con l,r sao cho tổng đoạn con chia hết cho K.

Input

• Dòng đầu là 2 số nguyên N và K.

• Dòng hai là N số nguyên dương a[i] ~(1 ≤ ai≤ 10^1~~^8)~.

Output

• Kết quả theo yêu cầu đề bài.

Giới hạn

Không giới hạn gì thêm

Ví dụ

Sample input

5 2
1 2 1 2 1

Sample output

6