AT_abc423_f [ABC423F] Loud Cicada

AtCoder 島には $ N $ 種類のセミが生息しています。種類 $ i $ のセミ ( $ 1 \leq i \leq N $ ) は $ A_i $ の倍数の年にのみ大量発生します。 $ 1 $ 年から $ Y $ 年までの $ Y $ 年間のうち、ちょうど $ M $ 種類のセミが大量発生する年が何回あるかを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Y $ $ A_1 $ $ \cdots $ $ A_N $

答えを出力せよ。

### Sample Explanation 1 $ 1 $ 年から $ 16 $ 年までのうち、各種類のセミが大量発生するのは以下の年です。 - 種類 $ 1 $ のセミは $ 4,8,12,16 $ 年に大量発生する。 - 種類 $ 2 $ のセミは $ 2,4,6,8,10,12,14,16 $ 年に大量発生する。 - 種類 $ 3 $ のセミは $ 3,6,9,12,15 $ 年に大量発生する。 $ 1 $ 年から $ 16 $ 年までのうち、ちょうど $ 2 $ 種類のセミが大量発生するのは $ 4,6,8,16 $ 年の $ 4 $ 回です。 ### Sample Explanation 2 答えが 32bit 整数に収まらないことがあります。 ### Sample Explanation 3 入力される値が 32bit 整数に収まらないことがあります。 ### Constraints - $ 1 \leq M \leq N \leq 20 $ - $ 1 \leq Y \leq 10^{18} $ - $ 1 \leq A_i \leq 10^{18} $ ( $ 1 \leq i \leq N $ ) - 入力される値はすべて整数