소소고금

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

엄밀하게는 $1 \le l \le r \le N$인 $(l, r)$ 쌍 중 $K \mid \sum_{i=l}^{r}S_i2^{r-i}$를 만족하는 쌍의 개수를 구하면 된다.

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

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

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