一个未知的数组 $x$ 包含 $N$ 个整数。该数组的 $K$-summary 是通过将数组划分为长度为 $K$ 的连续段，并对每个段中的元素求和得到的。如果 $N$ 不能被 $K$ 整除，则划分的最后一段将包含少于 $K$ 个元素。

换句话说，$K$-summary 是一个数组，其元素依次为：$(x[1] + \dots + x[K])$，$(x[K+1] + \dots + x[2K])$，依此类推，其中包含 $x[N]$ 的最后一项和可能包含少于 $K$ 个加数。例如，一个包含 $13$ 个元素的数组的 $5$-summary 包含三个元素（第 1~5 个元素的和、第 6~10 个元素的和、第 11~13 个元素的和）。

显然，我们无法仅从单个 $K$-summary 中重构出原数组的元素，但如果我们知道针对不同 $K$ 值的多个 $K$-summary，这就有可能实现。编写一个程序，在给定长度 $N$ 和集合 $K_1, K_2, \dots, K_M$ 的情况下，预测如果我们知道该数组的所有 $K_i$-summary，我们能够唯一确定原数组中的多少个元素。（不难证明，可重构的元素数量与 summary 的具体数值无关。）

输入格式

第一行包含整数 $N$ 和 $M$（$3 \le N \le 10^9$，$1 \le M \le 10$），分别表示数组长度和 $K$-summary 的数量。

第二行包含 $M$ 个互不相同的整数 $K_1, K_2, \dots, K_M$（$2 \le K_i < N$）。

输出格式

输出能够唯一确定的元素数量。

子任务

在占总分 40% 的测试数据中，满足 $N \le 5\,000\,000$。

样例

输入样例 1

3 1
2

输出样例 1

1

输入样例 2

6 2
2 3

输出样例 2

2

输入样例 3

123456789 3
5 6 9

输出样例 3

10973937

说明

样例 1 说明：我们可以确定一个元素：$x[3]$。

样例 2 说明：我们可以确定 $x[3]$ 和 $x[4]$。