问题描述

小A有一个长度为 $n$ 的数字序列，她希望从中选取两个不同的元素 $a_i$ 和 $a_j$，使得它们的乘积 $a_i \times a_j$ 的末尾至少有 $z$ 个连续的零。现在她想计算满足条件的选取方式的方案数。

输入格式

• 第一行输入两个整数 $n$ 和 $z$，分别表示序列的长度和所需零的个数。
• 第二行输入 $k$ 个正整数 $a_1, a_2, \dots, a_k$，表示给定的序列。

输出格式

输出一个整数，表示满足条件的选取方式的方案数。

样例输入

5 2
3 5 50 2 80

样例输出

3

说明

1. $5 \times 80 = 400$，末尾有 $2$ 个 $0$ 。
2. $50 \times 2 = 100$，末尾有 $2$ 个 $0$ 。
3. $50 \times 80 = 4000$，末尾有 $3$ 个 $0$ 。

以上共有 $3$ 种方案满足乘积结果至少有 $2$ 个末尾 $0$。

数据范围

$30\%$ 的数据，$1\leq n \leq 1000$

$100\%$的数据，$1 \leq n, z \leq 10^5$，$1 \leq a_i \leq 10^9$ 。