题目内容

给定一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$ 和一个正整数 $K$。

我们称一个子数组 $[l, r]$ 的“强度”为其所有元素乘积能被 $10$ 的多少次幂整除。若该子数组的乘积能被 $10^{K}$ 整除，即乘积中因子 $2$ 和因子 $5$ 的个数均不少于 $K$，则称该子数组为 $K$-强子数组。

请你统计满足条件的 $K$-强子数组的总数量。

数据范围：

• 数组长度 $n$ 满足 $1 \le n \le 2 \times 10^5$。
• $K$ 满足 $1 \le K \le 10^9$。
• 数组中的每个元素 $a_i$ 满足 $1 \le a_i \le 10^9$。

输入描述

第一行包含两个整数 $n$ 和 $K$，分别表示数组长度和所需的整除指数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示数组元素。

输出描述

输出一个整数，表示所有元素乘积能被 $10^{K}$ 整除的子数组个数。

样例1

输入

3 1
2 5 1

输出

2

说明

子数组 [2,5] 的乘积为 10，含有 1 个因子 2 和 1 个因子 5，满足 $K=1$； 子数组 [2,5,1] 的乘积同样为 10，也满足条件。 因此共有 2 个满足条件的子数组。

样例2

输入

2 10
100 100

输出

0

说明

每个 100 含有 $2^2 \times 5^2$，两个 100 相乘最多含有 4 个因子 2 和 4 个因子 5，均小于 $K=10$。 因此不存在任何子数组满足条件，答案为 0。

样例3

输入

4 2
100 25 4 5

输出

6

说明

元素因子个数： 100 含有 $2^2$ 和 $5^2$； 25 含有 $5^2$； 4 含有 $2^2$； 5 含有 $5^1$。

满足因子 2 和 5 的个数均不少于 2 的子数组有： [100]、[100,25]、[100,25,4]、[100,25,4,5]、[25,4]、[25,4,5]，共 6 个。