H. Reflexos no mostrador

Time limit: 4000 msMemory limit: 256 MB

Um mostrador tem $M$ posições, numeradas de $0$ a $M-1$ . Há $n$ botões disponíveis, identificados de $1$ a $n$ . O botão $i$ tem um parâmetro $a_i$ e, quando pressionado na posição $x$ , leva o marcador à posição $(a_i-x)\bmod M$ , usando o resto entre $0$ e $M-1$ .

Você escolherá um subconjunto dos botões para instalar. Começando na posição $0$ , será permitido pressionar os botões instalados em qualquer ordem e quantas vezes quiser, inclusive nenhuma vez.

Conte quantos subconjuntos permitem alcançar todas as posições. Para cada posição, pode-se usar uma sequência diferente de botões. Botões com parâmetros iguais continuam sendo botões distintos na contagem dos subconjuntos.

Input

A primeira linha contém $M$ e $n$ ( $1\le M,n\le 200000$ ). A segunda linha contém $a_1,\ldots,a_n$ ().

Output

Imprima o número de subconjuntos válidos módulo $998244353$ .

Samples

Sample 1

Input

4 3
0 1 3

Output

Os subconjuntos válidos de identificadores são $\{1,2\}$ , $\{1,3\}$ , $\{2,3\}$ e $\{1,2,3\}$ .

H. Reflexos no mostrador

Input

Output

Samples

Sample 1

Sample 2

Sample 3