Johnny has been sick lately and he missed a few classes. He didn’t make much of it with a single exception: physics is his passion, so he borrowed lecture notes from his friend. From those notes he learned that he missed lecture about Bohr model of hydrogen atom and… apparently he didn’t learn anything else, because based on the notes he reconstructed the following “Johnny-Bohr model”[^1]

The electron orbiting around nucleus of a hydrogen atom can only stay at orbits with specific radii. Each of those radii is associated with a particular energy of the electron and its angular momentum. The angular momentum is quantized, that is, it can take any value that is a positive integer multiple of the reduced Planck constant $\hbar$ (also known as Dirac constant). Due to this it is useful to number orbits with natural numbers, such that orbit number $n$ corresponds to angular momentum of $n\cdot\hbar$. An electron can jump from orbit $n_1$ to a lower orbit $n_2$ ($n_2<n_1$) — in that case the energy difference is emitted as a photon with appropriate frequency and wavelength. Johnny-Bohr model does not foresee the opposite situation, that is, absorption of a photon by atom and transfer of an electron to a higher orbit. The model precisely specifies to which lower orbits an electron can jump. In his friend’s notebook a multiset $B$ is written which has the following property: an electron can jump from orbit $a$ to an orbit $\lfloor a/b\rfloor$ for any $b\in B$. The electron can then jump from a new orbit $a'$ again according to that rule. In particular the Johnny-Bohr model allows an electron to jump to the (final) orbit number $0$, that is, to “fall” onto the nucleus. Just as with the original Bohr model, Johnny can’t prove that this model really describes the way hydrogen atom behaves, however he can assure you that it agrees with experimental data (at least the data from Johnny’s thought experiments). Proud of his deep understanding of the problem, Johnny noticed that it gives raise to a few interesting questions which may help him better understand the way atoms behave. The most important of the questions is the following: “If an electron starts at an orbit number $n$, to how many different orbits (including $n$) can the electron move in any number (possibly zero) of jumps?”

Input

The first line of input file contains two integers $n$ and $m$ ($1\le n\le 10^{15}$, $1\le m\le 10$), denoting the starting orbit number of the electron and the size of multiset $B$, respectively. The second (and last) line of input file contains sequence of $m$ integers $b_i$, $1\le b_i\le 10^{15}$, separated by single spaces; those are the elements of the multiset $B$.

Output

In the first and only line you should output a single integer – the number of different orbits on which the electron could end up after any number of jumps starting from orbit number $n$.

Examples

Input 1

20 2
2 3

Output 1

8

Note

Starting from an orbit $n=20$ and with $B=\{2,3\}$, an electron can jump (in 0 or more jumps) to any of the following eight orbits: $20,10,6,5,3,2,1,0$.

[^1]: Even though the model has name of one of the greatest physicists it has not much to do with physics: Johnny’s friend isn’t particularly skilled when it comes to taking notes, and Johnny’s fever is not helping!