배수 구간

자연수로 이루어진 배열 $A = [a_1, a_2, \ldots, a_n]$이 주어집니다. 배열 $A$에서 $l$번째부터 $r$번째까지의 원소로 이루어진 부분을 구간 $[a_l, a_{l+1}, \ldots, a_r]$이라고 합니다.

배열 $A$와 정수 $k$가 주어졌을 때, 구간의 합이 $k$로 나누어떨어지는 $(l, r)$ 쌍의 개수를 구하세요. 단, $l \le r$입니다.

첫 줄에 $A$의 원소 개수 $n$과 정수 $k$가 주어집니다 ($1 \le n \le 200\,000$, $2 \le k \le 10^9$).

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$이 주어집니다 ($1 \le a_i \le 10^9$).

조건을 만족하는 $(l, r)$ 쌍의 개수를 한 줄에 출력하세요. 여기서 $l \le r$이고, $l$부터 $r$까지 구간의 합이 $k$로 나누어떨어져야 합니다.

예제에서 조건을 만족하는 구간은 다음과 같습니다.

• $l = 1$, $r = 3$, 구간 $[1, 2, 3]$
• $l = 1$, $r = 4$, 구간 $[1, 2, 3, 4]$
• $l = 2$, $r = 2$, 구간 $[2]$
• $l = 2$, $r = 5$, 구간 $[2, 3, 4, 5]$
• $l = 3$, $r = 5$, 구간 $[3, 4, 5]$
• $l = 4$, $r = 4$, 구간 $[4]$