[POI2011] SEJ-Strongbox

题目描述

有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：若 $a$ 和 $b$ 是它的密码，则 $(a+b)\bmod 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}$