33275번 - 소소고금

문제

0ドル$과 1ドル$로만 이루어진 길이 $N$의 이진 문자열 $S$가 주어진다. $S$의 부분 문자열 중 이를 이진법 표기로 생각했을 때의 값이 $K$의 배수인 것의 수를 구하여라. 단, 부분 문자열의 첫 원소가 0ドル$이어도 된다.

엄밀하게는 $S_1S_2 \cdots S_N$에서 $K \mid \sum_{i=l}^{r}S_i2^{r-i}$ $(1 \le l \le r \le N)$인 $(l, r)$ 쌍의 수를 구하면 된다.

입력

첫째 줄에 문자열의 길이 $N$과 양의 정수 $K$가 공백으로 구분되어 주어진다. $(1 \leq N, K \leq 500,000円)$

둘째 줄에 문자열 $S$가 주어진다. $S$는 0ドル$과 1ドル$로만 구성되어 있다.

출력

이진법 표기로 생각했을 때의 값이 $K$의 배수인 부분 문자열의 수를 출력한다.

제한

힌트