题目描述

现在，你有一个长度为 $n$ 巨大无比的数 A。为了方便描述它，我们在这里将它的数字从左往右标号为 $1,2,3,\cdots,n$，第 $i$ 个数字为 $a_i$ ，即 $A = \overline{a_1 a_2 a_3 \cdots a_n}$。其中 $\overline{a_1 a_2 a_3 \cdots a_n}$ 表示一个数字等于 $a_1 \times 10^{n - 1} + a_2 \times 10^{n - 2} + a_3 \times 10^{n - 3} + \cdots + a_n \times 10^0$。

定义 $f(i, j) = \overline{a_i a_{i + 1} a_{i+2} \cdots a_j}$。

现在需要你数清，有多少对 $(i,j)$ ($i \le j$) 满足 $2^k$ 整除 $f(i, j)$ 且 $f(i,j)$ 没有多余的前导$0$。

对于数字 $010$ 有多余的前导 $0$，但是对于数字 $0$ 没有。

输入格式

第一行输入两个数字 $n, k$，意义如题目描述。

第二行输入一个长度为 $n$ 的字符串，这个字符串由 $0$ 到 $9$ 的数字组成。

输出格式

输出一行一个数字，为题目中所求。

样例输入

5 2
52012

7

样例解释

$7$ 个符合条件的 $f(i,j)$ 分别为: $f(1,2),f(1,3),f(1,5),f(2,3),f(2,5),f(3,3),f(4,5)$

数据范围

对于 $30\%$ 的数据，$n \le 18$

对于 $60\%$ 的数据，$n \le 1000$

对于另外 $20\%$ 的数据，$k = 0$

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le k \le 18$。