問題文

正整数 $N,M$ と長さが $M$ の正数列 $A$ が与えられます。

以下の方法で関数 $f(a, b)$ を定義します。

頂点に$0,1,...,N-1$ の番号がついた $N$ 頂点を用意し、変数 $X:=a-1, Y:=(X-b)mod\ a$ とします。 そして以下の操作を行います。

• 頂点 $X$ から 頂点 $Y$ へ有向辺を張る。
• $X=Y$, $Y=(Y-b)mod\ a$ とする。
• もし頂点 $a-1$ を始点, 終点とする閉路が存在すれば、 $f(a,b) = $ 閉路に含まれる最小の頂点番号 と定め、操作を終了する。
  
• またこの時閉路は単純閉路とし、そのような閉路は $1$ 通りに定まることが保証されます。(21:52追記)
そうでなければ操作を最初から繰り返す。

このとき $\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$ を求めてください。

入力

$N$ $M$
$A_0$ $A_1$ ...$A_{M-1}$

・入力は全て整数である。
・$1 \le N,M \le 10^6$
・$1 \le A_i \le N$

出力

$\sum_{i = 0}^{M-1}\sum_{j = 1}^{A_i}f(A_i,j)$ を求めてください。最後に改行してください。

サンプル

3 1
3

2

100 5
23 34 54 99 57

746