AT_s8pc_2_b.Division 2

兔子目前参加着一个编程竞赛，并处在 Division $2$ ，却一直难以晋升到 Division $1$。因此，兔子对将一个整数除以 $2$ 这种操作心怀不满。

现在，兔子在黑板上写下了从 $1$ 到 $n$ 的所有整数，并计划进行 $q$ 次操作。每次操作的规则如下：

• 在第 $i$ 次操作时，找到黑板上所有能被 $a_i$ 整除的数，并将这些数仅除以 $a_i$ 一次。

经过这些操作后，黑板上会剩下多少个数字是 $1$？

输入由以下格式给出：

• 第一行包含两个整数 $n$ 和 $q$，它们分别表示黑板上的数字数量和计划的操作次数。
• 接下来的 $q$ 行，每行包含一个整数 $a_i$，表示第 $i$ 次操作中用于除数的具体数值。

请输出一个整数，表示经过所有操作后，黑板上剩下的数字 $1$ 的总个数。

约束条件

• $ 1 \le n \le 10^{13} $
• $ 1 \le q \le 24 $
• $ 3 \le a_i \le 50 $

子任务

• 子任务 1 [25 分]: 满足 $ 1 \le n \le 10^6 $。
• 子任务 2 [75 分]: 无额外约束。

样例解释

样例 1:

初始化黑板上的数字为：1 2 3 4 5 6 7。

经过第一次操作，3 为除数：1 2 1 4 5 2 7。

经过第二次操作，6 为除数：1 2 1 4 5 1 7。

最终结果：有数量为 $3$ 和 $6$ 的数字变成了 $1$。

样例 2:

初始化黑板上的数字为：1 2 3 4 5 6 7。

经过第一次操作，6 为除数：1 2 3 4 5 1 7。

经过第二次操作，3 为除数：1 2 1 4 5 1 7。

最终结果：数量为 $1$、$3$、和 $6$ 的数字共 $3$ 个变成了 $1$。

样例 3:

初始化黑板上的数字为：1 2 3 4 5 6 7 8。

经过第一次操作，4 为除数：1 2 3 1 5 6 7 2。

经过第二次操作，8 为除数依然保持：1 2 3 1 5 6 7 1。

接下来的操作中，不再有变化，最终$1$，$4$ 四个数字变成了$1$。

本翻译由 AI 自动生成