题目描述

小迪老师突发奇想，决定定义 k 因数为因数和大于等于 k 的数字。例如当 $k = 15$ 时：

• 数字 $10$ 就是 k 因数，因为 $10$ 的因数有：1、2、5、10，因数和为 $1 + 2 + 5 + 10 = 18$，而 $18 \geq 15$。
• 数字 $11$ 就不是 k 因数，因为 $11$ 的因数有：1、11，因数和为 $1 + 11 = 12$，而 $12 < 15$。

现在给出 $n$ 个整数 $a_1、a_2、……、a_n$，请问有多少对数字组合 $<a_i, a_j>$ 符合以下要求：

• $i < j$
• $j - i > k \% n$
• $a_i$ 和 $a_j$ 都是 k 因数。

输入格式

第一行输入 $2$ 个整数 $n、k(1 \leq n \leq 10^6, 1 \leq k \leq 10^9)$。

第二行输入 $n$ 个整数 $a_i(1 \leq a_i \leq 10^6)$。

输出格式

输出一个整数，代表符合要求的数字组合的数量。

样例

5 15
10 11 6 8 12

3

样例解释

当 $k = 15$ 时：

• 数字 $10$ 是 k 因数，因为 $10$ 的因数有：1、2、5、10，因数和为 $1 + 2 + 5 + 10 = 18$，而 $18 \geq 15$。
• 数字 $11$ 不是 k 因数，因为 $11$ 的因数有：1、11，因数和为 $1 + 11 = 12$，而 $12 < 15$。
• 数字 $6$ 不是 k 因数，因为 $8$ 的因数有：1、2、3、6，因数和为 $1 + 2 + 3 + 6 = 12$，而 $12 < 15$。
• 数字 $8$ 是 k 因数，因为 $8$ 的因数有：1、2、4、8，因数和为 $1 + 2 + 4 + 8 = 15$，而 $15 >= 15$。
• 数字 $12$ 是 k 因数，因为 $12$ 的因数有：1、2、3、4、6、12，因数和为 $1 + 2 + 3 + 4 + 6 + 12 = 28$，而 $28 >= 15$。

此时 $n = 5$，$k = 15$，$k \% n = 0$，下标差值 $j - i > 0$ 总是成立，会有以下数字组合符合要求：

• $a_1 = 10$ 和 $a_4 = 8$ 是一对组合。

• $a_1 = 10$ 和 $a_5 = 12$ 是一对组合。

• $a_4 = 8$ 和 $a_5 = 12$ 是一对组合。

总共有 $3$ 对组合。

数据约束