문제 설명
\(N\)개의 수 \(A_1, A_2, ... , A_N\)이 주어졌을 때 연속된 부분의 합이 \(M\)으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.
즉, \(A_i + ... + A_j (i \le j) \)의 합이 \(M\)으로 나누어떨어지는 \((i, j)\) 쌍의 개수를 구한다.
즉, \(A_i + ... + A_j (i \le j) \)의 합이 \(M\)으로 나누어떨어지는 \((i, j)\) 쌍의 개수를 구한다.
입력 설명
1번째 줄에 \(N\)과 \(M(1 \le N \le 10^6, 2 \le M \le 10^3)\)이 입력된다.
2번째 줄에 N개의 수 \(A_1, A_2, ..., A_N\)이 주어진다.\((0 \le A_i \le 10^9)\).
2번째 줄에 N개의 수 \(A_1, A_2, ..., A_N\)이 주어진다.\((0 \le A_i \le 10^9)\).
출력 설명
1번째 줄에 연속된 부분의 합이 \(M\)으로 나누어떨어지는 구간의 개수를 출력한다.
입력 예시 Copy
5 3
1 2 3 1 2
출력 예시 Copy
7