题目描述

译自 POI 2011 Round 2. Day 0. A「Strongbox」

Byteasar 是一个有名的保险柜盗贼，但他最近宣布金盆洗手，并从事测试和认证防盗装置的工作。他刚刚收到一种新型保险柜并将要测试，这种保险柜是一种组合式保险柜，虽然都是用类似拨号盘的圆盘打开，但与一般组合保险柜有一些不同。拨号盘指针可以置于 $n$ 个不同的位置上，编号为 $0$ 到 $n-1$。将指针转至某些位置就能打开保险柜，转至其他位置就打不开。而对于这种组合式保险柜，如果指针转至 $x$ 和 $y$ 的时候能打开保险柜，那么转至 $(x+y)\bmod n$ 处也能打开保险柜。注意这里 $x=y$ 时也满足条件。

Byteasar 尝试了拨号盘上 $k$ 个不同的位置：$m_1,m_2,\ldots ,m_k$。当转至 $ m_1, m2, \ldots, m{k - 1} $ 时，保险柜没有打开，只有转到 $m_k$ 时保险柜打开了。Byteasar 已经试了 $k$ 次，他已经不想继续试下去了。基于他已经试过的位置信息，他想知道最多可能有多少位置当指针转至此位置时能打开保险柜。请写一个程序帮助他解决这个问题。

输入格式

第一行两个整数 $n,k$；

接下来 $k$ 个不同的整数 $m_1,m_2,\ldots ,m_k$。

输出格式

输出一个整数，表示最后所求答案。

样例

input

42 5
28 31 10 38 24

output

14

数据范围与提示

对于全部数据，$ 1 \le k \le 250000, k \le n \le 10^{14} $。

对于 $70\%$ 的分数，保证 $k\le 1000$；

在这 $70\%$ 的分数中，有 $20\%$ 的分数保证 $n\le 10^8,k\le 100$。

Task author: Marian M. Kedzierski.