入力

入力は以下の形式で標準入力から与えられる。

n q
a_1
:
a_q

• 1 行目には, 黒板に書く数の個数n と処理の回数qが空白区切りで与えられる。
• 2 行目から, q 行にわたって a_i が与えられる。 a_i は i 番目の処理で割る数を表す。

出力

出力は以下の形式で標準出力に従うこと。

• 最終的に、黒板に「1」が何個書かれているか、1行で出力してください。

制約

• 1 ≦ n ≦ {10}^{13}
• 1 ≦ q ≦ 24
• 3 ≦ a_i ≦ 50

小課題

小課題 1 [ 25 点 ]

• 1≦n≦10^6 を満たす。

小課題 2 [ 75 点 ]

• 追加の制約はない。