题目描述

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

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

输入格式

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

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

数据保证存在合法解。

输出格式

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

样例

输入样例

42 5
28 31 10 38 24

输出样例

14

提示

对于$\red{10\%}$的数据:$\red{N≤}$$\red{10^4 ,k≤}$$\red{100}$;

另有$\red{10\%}$的数据:$\red{N≤}$$\red{10^9 ,k≤}$$\red{100}$;

另有$\red{10\%}$的数据:$\red{N≤}$$\red{10^9,k=1}$;

对于前$\red{60\%}$的数据:$\red{k≤}$$\red{1 000}$;

对于$\red{100\%}$的数据:$\red{1≤}$$\red{k≤}$$\red{250 000,k≤}$$\red{n≤}$$\red{10^{14}}$;