题目描述

有一个长度为 $N$ 的未知数组 $x$。这个数组的 $K$-总和定义为将该数组分割为若干长度为 $K$ 的区间，并对每个区间中的元素分别求和的结果。如果 $N$ 不能被 $K$ 整除，则最后一个区间的元素数将少于 $K$。

换言之，$K$-总和指的是一个数组，其中的元素分别为：$(x_1+\dots+x_K)$，$(x_{K+1}+\dots+x_{2K})$，以此类推；其中包含了 $x_N$ 的元素，即最后一个元素，可以由少于 $K$ 个部分组成。例如，一个含有十三个元素的数组的 $5$-总和有三个元素（第一到第五项之和，第六到第十项之和，第十一到第十三项之和）

可以发现我们无法通过一个 $K$-总和来重现原数组，但当我们知道几个 $K$ 值不同的 $K$-总和时就有可能做到这一点。给定 $N$ 和 $K_1,K_2,\dots,K_M$，请您编写一条程序，计算在已知一个长为 $N$ 的数组的 $K_i$-总和的前提下，有多少原数组的元素可以被唯一确定（不难发现唯一确定的元素数与 $K_i$-总和的内容无关）。

输入格式

第一行包含两个整数 $N$ 和 $M$，$N$ 为原数组大小，$M$ 为已知 $K$-总和的数量。

第二行包含 $M$ 个整数，分别为 $K_1,K_2,\dots,K_M$，如题所述。

输出格式

您需要输出唯一确定的元素数。

输入输出样例 #1

输入 #1

3 1
2

输出 #1

1

输入输出样例 #2

输入 #2

6 2
2 3

输出 #2

2

输入输出样例 #3

输入 #3

123456789 3
5 6 9

输出 #3

10973937

说明/提示

对于 $40\%$ 的数据，$N\le5\times10^6$。

对于 $100\%$ 的数据，$3\le N\le10^9$，$1\le M\le10$，$2\le K_i<N$。

样例解释

对于第一个样例：我们可以确定 $x_3$。

对于第二个样例：我们可以确定 $x_3$ 和 $x_4$。

翻译来自于 @阿丑