#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

#define mt(a) memset(a,0,sizeof(a))

using namespace std;

const int mod=;

typedef long long ll;

ll a[];

ll num[];

ll cnt[];

ll get(ll n)

{

    int f=;

    f=n*n;

    f%=mod;

    return f;

}

int main()

{

    ll n;

    while(~scanf("%lld",&n))

    {

        ll mx=-;

        mt(a);

        mt(cnt);

        mt(num);

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

        {

            scanf("%lld",&a[i]);

            num[a[i]]++;

            mx=max(mx,a[i]);

        }

        ll ans=;

        for(ll i=mx;i>=;i--)

        {

            int ret=num[i];

            for(int j=i*;j<=mx;j+=i)

            {

                cnt[i]=(cnt[i]-cnt[j]+mod)%mod;

                ret+=num[j];

            }

           // cout<<ret<<endl;

            cnt[i]+=get(ret);//想清楚。

            cnt[i]+=mod;

            cnt[i]%=mod;

            ll p=i*(i-)%mod;

            ans=(ans+(cnt[i]*p))%mod;

        }

        cout<<ans<<endl;

    }

    return ;

}