T1 变形怪

题目信息

时间限制: 1s

空间限制: 512M

输入文件: set.in

输出文件: set.out

题目描述

小智邂逅了一只变形怪，这只变形怪一共可以变形成 $n+1$ 种不同的形态，用 $0, 1,\dots, n$ 编号，变形怪的初始形态是 $n$，且必须在变形试剂的刺激下才能发生形态变化。

为了锻炼变形怪的变形技能，小智下血本在 pdd 买了一袋变形试剂盲盒，盲盒里有 $m$ 支属性可能重复的变形试剂。每支变形试剂都有一个属性 $x_i$，当变形怪处于形态 $k$ 时，使用属性为 $x_i$ 的变形试剂，变形怪会变形成形态 $\left\lfloor \frac{k}{x_i}\right\rfloor$。

变形怪可以随时变回初始形态 $n$，盲盒里的所有试剂都是可以无限使用的，那么小智能将变形怪变成多少种不同的形态呢？

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，含义如题所示。

接下来一行，包含 $m$ 个整数 $x_1,x_2,\cdots, x_m$，描述变形试剂盲盒中的试剂的属性。因为是 pdd 买的，所以盲盒中可能包含相同的属性的试剂。

输出格式

输出一行一个整数，表示答案。

样例

样例输入 1

7 2
2 3

样例输出 1

5

样例解释 1

• $n=7$：初始状态
• $n=3$：在 $n=7$ 时令 $x=2$
• $n=2$：在 $n=7$ 时令 $x=3$
• $n=1$：在 $n=2$ 时令 $x=2$
• $n=0$：在 $n=2$ 时令 $x=3$

样例输入 2

12 4
1 2 4 5

样例输出 2

6

数据范围与提示

对于所有数据，$1 \le n \le 10^{15}$，$1 \le x \le 10^{15}$，$1 \le m \le 10$。