题目描述

$ATC$ 岛上有 $N$ 个蝉的种类。第 $i$ 种蝉（$1\le i\le N$）在年份为 $A_i$ 的倍数的年份发生大量爆发。

在从第 $1$ 年到第 $Y$ 年的这 $Y$ 年中，统计有多少个年份恰好有 $M$ 个种类的蝉发生大量爆发。

约束

输入格式

输入共两行：

• 第 $1$ 行给出 $N$、$M$、$Y$，
• 第 $2$ 行给出 $A_1,\dots,A_N$。

输出格式

输出一个整数，表示从年份 $1$ 到年份 $Y$ 中恰好有 $M$ 个种类蝉大量爆发的年份个数。

样例输入 1

3 2 16
4 2 3

样例输出 1

4

样例输入 2

2 1 122333444422333
1429 73651

样例输出 2

87266392324

样例输入 3

20 3 832725971730072237
19639596380058 49098990950145 32732660633430 114564312217005 68738587330203 45825724886802 252041486877411 180029633483865 108017780090319 72011853393546 468077047058049 297867211764213 212762294117295 127657376470377 85104917646918 723391799998803 612100753845141 389518661537817 278227615384155 166936569230493

样例输出 3

24231

说明

样例 1 解释

从 $1$ 到 $16$ 年中，各种蝉爆发年份如下：

• 第 $1$ 种：$4,8,12,16$；
• 第 $2$ 种：$2,4,6,8,10,12,14,16$；
• 第 $3$ 种：$3,6,9,12,15$。

恰好有两种蝉爆发的年份为 $4,6,8,16$，共 $4$ 年。

数据范围

• $1\le M\le N\le 20$
• $1\le Y\le 10^{18}$
• $1\le A_i\le 10^{18}\ (1\le i\le N)$
• 所有输入值均为整数。
• 输入值可能无法放入 $32$ 位整数类型，请使用合适的 $64$ 位或更高精度类型处理。