소소고금

$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$의 배수인 부분 문자열의 수를 출력한다.