F - Contando juegos

Time limit: 1 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

Dos amigos están jugando con $N$ piedras en un montón. Al inicio del juego ambos se ponen de acuerdo en la cantidad de piedras que van a usar y en las jugadas válidas. Después ambos jugadores van turnándose alternadamente hasta que no puedan hacer más movimientos. En un turno un jugador selecciona un movimiento y elimina dicha cantidad de piedras de la pila. El primer jugador que no puede hacer ningún movimiento pierde. Los dos amigos son muy buenos jugadores y siempre van a seguir la mejor estrategia para intentar ganar. Al inicio la cantidad de piedras con que juegan se selecciona al azar para evitar ventajas. Incluso con esta medida el segundo jugador se queja y decide contar de todos los posibles juegos que pueden disfrutar con las $N$ piedras en cuántos de ellos puede ganar seguro. Tenga en cuenta que el juego debe comenzar con al menos una piedra y que no puede tener más de $N$ que es el total de piedras en el montón.

Input

La primera línea de la entrada tiene dos enteros $N (1 \le N \le 10 ^ 9)$ y $M (1 \le M \le 22)$, representado la cantidad de piedras que pueden usar y la cantidad de movimientos posibles respectivamente. La próxima línea consiste en $M$ enteros positivos $m_i$ separados por un espacio. Cada $m_i (1 \le m_i \le 22)$ es un posible movimiento.

Output

Se debe imprimir la cantidad de juegos que puede ganar el segundo jugador con los movimientos definidos y la cantidad máxima de piedras dada.

Sample test(s)

Input
5 2 1 2
Output
1

Hints