Divide GCD

2 secs 1024 MB
sgsw

問題文


(2/11 : 修正が完了しました)

個の自然数からなる整数列があります.

やちよさんは,自然数列を以下の条件を満たすようにいくつかの空でないグループに分割することにしました.


◎いずれの要素もちょうどつのグループに属する


さらに,やちよさんはこの分割によって得られたグループに対し,以下でその分割に対するスコアを定めました.

全ての分け方に対するスコアの総和をとするとき,やちよさんのかわりにを求めてください.

ただし,そのままでは巨大な値になりうるためでわったあまりとして求めてください.


ただし,分割が同じであるかは以下によります.

◎任意のに対し,「においては同一のグループに属する」⇄「においては同一のグループに属する」

入力


N
A_1 A_2 ... A_N

出力


行にわたってを出力してください.

ただし,そのままでは巨大な値になりうるためでわったあまりを出力してください.

最後に改行してください.

制約


サンプル


入力1
8
2 6 9 12 3 6 15 8
出力1
109650

分割がの場合のスコアを考えましょう.

の場合,同じグループに属するすべての数の最大公約数はです.

の場合,同じグループに属するすべての数の最大公約数はです.

の場合,同じグループに属するすべての数の最大公約数はです.

同様にについても計算することでこの場合のスコアの値はであることがわかります.

他のすべての分割に対してもスコアを計算し,合計を取るとになります.

入力2
1
1234
出力2
1234
入力3
10
999000 928800 998910 992400 991200 95200 945600 993860 79800 99440
出力3
32347003

ですが,でわったあまりを出力してください.

Submit


Go (1.14)