시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.024 초 512 MB150997865.000%

문제

어떤 익명의 단체가 서강대학교 $K$관 512호에서 아무도 모르게 피자를 나눠 먹으려고 한다!

이 단체는 오랜 실험의 결과로 개인이 먹는 피자 덩어리의 무게가 마법의 수인 $K$의 배수이면 어떤 냄새도 남기지 않고 먹을 수 있다는 것을 알아냈다.

또한 이 단체는 특별히 지정된 피자 가게에서만 주문하기 때문에 항상 전체 무게가 $K$의 배수인 피자를 먹는다. 하지만 안타깝게도 각 조각의 무게가 균일하지 않기 때문에 조각을 어떻게 나눠 가져야 하는지 정하는 데 난항을 겪고 있다.

이 단체의 핵심 인물인 당신은 최대한 많은 사람이 피자를 나눠 먹을 수 있게 피자를 나눠 줘야 한다. 피자는 절취선 이외의 선으로는 자를 수 없다. 피자를 나눴다가 다시 붙여서 무게를 $K$의 배수로 바꾸는 일도 불가능하다. 따라서 처음부터 연결된 덩어리 중에서 무게가 $K$의 배수가 되게 자르는 경우만 생각하기로 한다.

예를 들어 $K$ = 512이고, 피자가 다음 그림과 같다고 하자.

1, 2번 조각을 합치면 무게가 512이고, 3, 4, 5, 6번 조각을 합치면 무게가 1024이므로 이렇게 두 덩어리로 나눌 수 있다. 3, 5번 조각을 합치면 무게가 512이고 4, 6번 조각을 합치면 무게가 512지만 서로 연결되어 있지 않기 때문에 그러한 경우는 생각하지 않는다.

사람들은 각각 자신이 얼마나 많이 먹게 될지는 신경 쓰지 않는다. 피자를 남김없이 나누면서 최대 몇 명의 사람이 무게가 $K$의 배수인 피자 덩어리를 나눠 받을 수 있을지 구해보자.

입력

첫 번째 줄에 피자 조각의 개수 $N$ $(1 \le N \le 1\,000\,000)$과 마법의 수 $K$ $(1 \le K \le 100\,000)$가 주어진다.

두 번째 줄에 특정 조각부터 시작해 시계 방향으로 각 조각의 무게를 나타내는 정수 $a_1, a_2, \cdots, a_N$ $(1 \le a_i \le 1\,000\,000)$이 공백으로 구분되어 주어진다.

단, 피자는 원형이기 때문에 마지막 조각과 첫 번째 조각은 서로 붙어있다.

출력

첫 번째 줄에 피자를 최대 몇 명에게 나눠줄 수 있는지 출력한다.

예제 입력 1

6 512
290 222 68 179 444 333

예제 출력 1

2

힌트

서강대학교 $K$관 512호에서는 피자를 먹으면 안 됩니다.