P3518 [POI 2011] SEJ-Strongbox

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

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

一行一个整数，表示答案。

### 数据规模与约定 对于约 $20\%$ 的数据，满足 $1\le k\le 100,n\le 10^{8}$。 对于约 $70\%$ 的数据，满足 $1\le k\le 1000$。 对于 $100\%$ 的数据，满足 $1\le k\le2.5\times10^5,k\le n\le 10^{14},0\le m