题目描述

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

输入格式

第一行n，k；
下面一行k个整数，表示每次试的密码，保证存在合法解。

输出格式

一行，表示结果。

样例数据

input

42    5
28     31    10    38    24

output

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。