Byteasar 是一位著名的保险箱破解专家，他已经放弃了犯罪活动，转而从事防盗装置的测试与认证工作。他刚刚收到一种新型保险箱进行测试：组合式保险箱。组合式保险箱与普通的密码保险箱不同，尽管它也是通过旋转拨盘来开启的。拨盘可以设置在 $0$ 到 $n-1$ 共 $n$ 个不同的位置。其中一些位置可以打开保险箱，而另一些则不能。该保险箱具有组合性质，这也是其名称的由来：如果 $x$ 和 $y$ 是开启位置，那么 $(x+y)\bmod n$ 也一定是开启位置；注意这对于 $x=y$ 的情况同样适用。

Byteasar 尝试了拨盘的 $k$ 个不同位置：$m_{1},m_{2},…,m_{k}$。其中位置 $m_{1},m_{2},…,m_{k-1}$ 均未能打开保险箱，只有最后一个位置 $m_{k}$ 可以。Byteasar 已经厌倦了检查这些位置，因此完全不打算尝试剩下的位置。然而，他想根据已知尝试过的信息，计算出能够打开保险箱的位置的最大可能数量。请编写一个程序来帮助他！

输入格式

输入的第一行包含两个整数 $n$ 和 $k$，由单个空格分隔，$1 \le k \le 250,000$，$k \le n \le 10^{14}$。第二行包含 $k$ 个不同的整数，同样由单个空格分隔，$m_{1},m_{2},…,m_{k}$，$0 \le m_{i} < n$。你可以假设输入数据对应于符合上述描述的某种组合式保险箱。

在约占 $70\%$ 分值的测试中，$k \le 1,000$。在其中约占 $20\%$ 分值的部分测试中，还满足以下条件：$n \le 10^{8}$ 且 $k \le 100$。

输出格式

程序应在标准输出的第一行（也是唯一一行）输出一个整数：能够打开保险箱的位置的最大数量。

样例

输入 1

42 5
28 31 10 38 24

输出 1

14