U473984 密码

有一个密码箱，$0$ 到 $n-1$ 中的某些整数是它的密码。且满足：如果 $a, b$ 都是它的密码，那么 $(a+b)\mod n$ 也是它的密码（$a,b$ 可以相等），某人试了 $k$ 次密码，前 $k - 1$ 次都失败了，最后一次成功了。 问：该密码箱最多有多少种不同的密码。

第一行两个整数 $n,k$。 \ 第二行 $k$ 个非负整数，表示每次试的密码。

一行一个整数，表示结果。

**【数据规模】** \ 对于 $100\%$ 的数据， $1≤k≤250000,k ≤ n ≤10^{14}$