Description

给出一个长为N的数列a,

求sigma(sigma(gcd(ai,aj)*gcd(i,j)))

1<=i<=N,1<=j<=N

Format

Input

第一行两个正整数N,N<=100000

接下来一行共n个正整数，其中第i个表示 ai 。

Output

输出一行一个数，表示答案，对于10^9+7 取模。

Samples

5
1 4 5 2 3

73