题目描述

有一个密码箱，0到$n$-1中的某些整数是它的密码。且满足：如果$a$和$b$都是它的密码，那么（$a+b$）％$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$

来源

• 信息学奥赛之数学一本通
• stong9070整理