#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define re register

const int N=1e6+;

const int mod=1e9+;

void read(int &a)

{

    a=;

    int d=;

    char ch;

    while(ch=getchar(),ch>''||ch<'')

        if(ch=='-')

            d=-;

    a=ch-'';

    while(ch=getchar(),ch>=''&&ch<='')

        a=a*+ch-'';

    a*=d;

}

void write(int x)

{

    if(x<)

        putchar(),x=-x;

    if(x>)

        write(x/);

    putchar(x%+'');

}

int a[N];

int GCD(int a,int b)

{

    return b==?a:GCD(b,a%b);

}

int main()

{

    int n;

    read(n);

    ll ans=,gcd;

    read(a[]);

    gcd=a[];

    for(re int i=;i<n;i++)

        read(a[i]),gcd=GCD(gcd,a[i]);

    for(re int i=;i<n;i++)

    {

        int now=a[i];

        for(re int j=i;j<n;j++)

        {

            if(now==gcd)

            {

                ans=(ans+(n-j)*gcd)%mod;

                break;

            }

            now=GCD(now,a[j]);

            ans+=now;

            ans%=mod;

        }

    }

    write(ans);

    return ;

}