Combinatorial Safe

Byteasar, a renowned safe-cracker, now analyzes anti-burglary devices. He is testing a combinatorial safe that has a rotary dial with n positions (numbered from 0 to n-1). Some positions open the safe and others do not. The safe has a special combinatorial property: if x and y are positions that open the safe, then so does (x+y) mod n (note that the property applies even when x = y).

Byteasar tried k different positions denoted by m₁, m₂, \ldots, m_k. The first k-1 attempts failed (the safe did not open), and only the last attempt, m_k, opened the safe.

The set of opening positions must then form a subgroup of \( \mathbb{Z}_n \). In fact, every subgroup of \( \mathbb{Z}_n \) is of the form \[ H_d = \{0, \frac{n}{d}, 2\cdot\frac{n}{d}, \ldots, (d-1)\cdot\frac{n}{d} \}, \] where \( d \) is a divisor of \( n \) and the subgroup has exactly \( d \) elements.

Based on his trials, Byteasar wants to know: What is the maximum possible number of positions that open the safe?

This is subject to the conditions that:

• The subgroup \( H_d \) must contain the opening position \( m_k \) (i.e. \( m_k \equiv 0 \; (\bmod\; \frac{n}{d}) \)).
• None of the other tried positions \( m_1, m_2, \ldots, m_{k-1} \) belong to \( H_d \) (i.e. for each m among these, \( m \not\equiv 0 \; (\bmod\; \frac{n}{d}) \)).

Your task is to help Byteasar by finding the maximum \( d \) (i.e. the largest subgroup size) for which such a subgroup may exist, or output 0 if no subgroup satisfies the conditions.

inputFormat

The first line contains two integers n and k (the number of positions on the dial and the number of tried positions, respectively).

The second line contains k integers: m₁, m₂, \ldots, m_k, where the first k-1 positions are non-opening and only m_k is an opening position.

outputFormat

Output a single integer representing the maximum possible number of positions that open the safe. If no valid subgroup exists based on the given conditions, output 0.

sample

10 3
1 2 4

0