GCD of Contiguous Subsequence 2

長さの数列が与えられます．「数列の空でない全ての連続部分列」における「連続部分列の長さ 全要素の最大公約数」の総和をで割ったあまりを求めてください．つまり，

をで割ったあまりを求めてください．

ただし，部分列の要素が同じでも、取り出す位置が異なっていれば別の部分列として数えます．

また，数列の要素がつの場合はその要素の値を最大公約数とします．つまり，任意の自然数について，です．

• 入力はすべて整数

をで割ったあまりを出力してください．

5
8 3 80 4 164

310

以下では をポイントと呼びます．

• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．
• の長さは，最大公約数はなのでポイントはです．

これらを合計するとになります．

5
12 12 12 12 6

330