Balancing the Game

In this problem, you are a game developer designing a game with the following elements:

• An enemy creature with health m.
• A weapon with n levels. The damage dealt by an attack using the level i weapon is i \times p, where p is an unknown positive integer.

Furthermore, you are given a sequence \(\{a_i\}_{i=1}^n\), where \(a_i\) means that when the enemy is attacked exactly \(a_i\) times with the level i weapon, the enemy dies. Note that all parameters are integers. This implies that when using the level i weapon repeatedly, the enemy's health satisfies the condition: \[ (a_i-1)\cdot i \times p < m \leq a_i \cdot i \times p. \]

Your task is to determine the number of possible values for \(p\) that satisfy all of the above conditions simultaneously. If there are infinitely many such \(p\), output xiaogougege.

inputFormat

The first line contains two integers m and n \( (1 \leq m \leq 10^9, 1 \leq n \leq 10^5) \) representing the enemy's health and the number of weapon levels respectively.

The second line contains \(n\) integers: \(a_1, a_2, \ldots, a_n\) \( (1 \leq a_i \leq 10^9) \), where \(a_i\) indicates that the enemy dies after being attacked exactly \(a_i\) times with the level i weapon.

outputFormat

Output a single integer denoting the number of possible positive integer values for \(p\) that satisfy the conditions. If there are infinitely many valid \(p\), output xiaogougege instead.

sample

10 1
1

xiaogougege