#604나머지 합

gold

⏱ 시간 제한: 1초|💾 메모리 제한: 256 MB

문제 설명

수 N개 A_1, A_2,..., A_N이 주어집니다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하세요.

즉, A_i +... + A_j (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 합니다.

첫째 줄에 N과 M이 주어집니다. (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3)

둘째 줄에 N개의 수 A_1, A_2,..., A_N이 주어집니다. (0 ≤ A_i ≤ 10^9)

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력합니다.

입력 1

5 3
1 2 3 1 2

출력 1