#include <bits/stdc++.h>
using namespace std;
#define ll long
int prime(ll x){
    if (x==2)
        return 1;
    else if (x%2==0)
        return 0;
    else {  
        for (int i=3;i*i<=x;i+=2)
            if (x%i==0)
                return 0;
        return 1;
    }       
}
int main() {  
    int n,i,j,k;
    cin>>n;
    bool mark[1000001]={0};
    mark[0]=1;mark[1]=1;
    for (i=4;i<=1000000;i+=2)
        mark[i]=1;
    for (int i=3;i*i<=1000000;i+=2){
        if (!mark[i])
            for (int j=i*i;j<=1000000;j+=2*i)
                mark[j]=1;
    }
    ll a,mod=1e9,sum=0;
    while (n--){
        cin>>a;
        if (a==1)
            sum=(sum+1)%mod;
       else if (prime(a))
           sum=(sum+a+1)%mod;
        else {
            i=sqrt(a);
            sum=(sum+1+a)%mod;
            k=1;
            while (a!=1){
                i=sqrt(a);
            for (j=i;j>=1;j--){
               if (a%j==0&&!mark[j]&&!mark[a/j]) {
                   sum=(sum+(a/j))%mod;
                   a=1;
                   j=0;
              
               }
                else if ((a%j)==0&&!mark[j]){
                   sum=(sum+k*j)%mod;
                    k=j;
                   a=a/j;     
                    j=0;
                }
               
                
            }
                
        }
            
    }
       
    }
   cout<<sum<<endl;
    return 0;
}