题目描述

有一个密码箱，$[0,n)$ 中的某些整数是它的密码，且满足，如果 $a$ 和 $b$ 都是它的密码，那么 $(a+b)\bmod n$ 也是它的密码（$a,b$ 可以相等）。

某人试了 $k$ 次密码，前 $k-1$ 次都失败了，最后一次成功了。

问：该密码箱最多有多少不同的密码。

输入格式

第一行两个整数 $n,k$。

下面一行 $k$ 个整数，表示每次试的密码。

保证存在合法解。

输出格式

一行一个整数表示答案。

42 5
28 31 10 38 24

14

数据规模与约定

对于 $100\%$ 的数据，$1\leq k\leq 2.5\times 10^5$，$k\leq n\leq 10^{14}$。