题目描述

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

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

输入格式

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

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

输出格式

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

42 5
28 31 10 38 24

14

提示

数据规模与约定

对于约 $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<n$。