题目描述

有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：如果 $a$ 和 $b$ 都是它的密码，那么 $(a+b)\%n$ 也是它的密码（$a,b$ 可以相等，$\%$ 表示整除取余数，下同），某人试了 $k$ 次密码，前 $k-1$ 次都失败了，最后一次成功了。

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

输入格式

输入第一行两个整数分别表示 $n,k$。

第二行为 $k$ 个用空格隔开的非负整数，表示每次试的密码。

数据保证存在合法解。

输出格式

输出一行一个数，表示结果。

42 5
28 31 10 38 24

14

数据范围

• 对于 $10\%$ 的数据：$N≤10^4$，$k≤100$
• 另有 $10\%$ 的数据：$N≤10^9$，$k≤100$
• 另有 $10\%$ 的数据：$N≤10^9$，$k=1$
• 对于前 $60\%$ 的数据：$k≤1000$
• 对于 $100\%$ 的数据：$1≤k≤250000$，$k≤n≤10^{14}$。