AT_s8pc_2_b Division 2

[problemUrl]: https://atcoder.jp/contests/s8pc-2/tasks/s8pc_2_b うさぎは, プログラミングコンテストで今 Division $ 2 $ であり, なかなか Division $ 1 $ に上がれない。 そのため, うさぎは整数を $ 2 $ で割ることに対して恨みを持っている。 ところで, 今, うさぎは, $ 1 $ から $ n $ までの数字を黒板に書き, 以下の操作を $ q $ 回しようとしている。 - $ i $ 回目の操作のとき, 黒板に書かれている数の中で $ a_i $ で割り切れるものがあればその数を $ a_i $ で $ 1 $ 回だけ割る。 最終的に $ 1 $ が何個残るでしょうか？

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 点 \] - 追加の制約はない。 ### Sample Explanation 1 数字は以下のように変化する。 1 2 3 4 5 6 7 3で割る 1 2 1 4 5 2 7 6で割る 1 2 1 4 5 2 7よって、$ 1,3 $の$ 2 $つの場合最終的に$ 1 $になる。 ### Sample Explanation 2 数字は以下のように変化する。 1 2 3 4 5 6 7 6で割る 1 2 3 4 5 1 7 3で割る 1 2 1 4 5 1 7よって、$ 1,3,6 $の$ 3 $つの場合最終的に$ 1 $になる。 ### Sample Explanation 3 数字は以下のように変化する。 1 2 3 4 5 6 7 8 4で割る 1 2 3 1 5 6 7 2 8で割る 1 2 3 1 5 6 7 2 16で割る 1 2 3 1 5 6 7 2 32で割る 1 2 3 1 5 6 7 2よって、$ 1,4 $の$ 2 $つの場合最終的に$ 1 $になる。