#include<fstream>
#include<iostream>
#define DN 705
#define DM 2005
#define M 30103
using namespace std;
ifstream fin("evantai.in");
ofstream fout("evantai.out");
int n,a[DN],dp1[DN][DM],val,t,rez,dp2[DN][DM];
int query2(int k,int poz,int dp[DN][DM])
{
    int s=0;
    for(;poz;poz-=(poz&(-poz)))
        s=(s+dp[k][poz])%M;
    return s;
}
int query1(int poz,int dp[DN][DM])
{
    int s=0;
    for(;poz;poz-=(poz&(-poz)))
        s=(s+query2(poz,2000,dp)+M-query2(poz,t,dp))%M;
    return s;
}
void update2(int k,int poz,int dp[DN][DM])
{
    for(;poz<=2000;poz+=(poz&(-poz)))
        dp[k][poz]=(dp[k][poz]+val)%M;
}
void update1(int poz,int dp[DN][DM])
{
    for(;poz<=n;poz+=(poz&(-poz)))
        update2(poz,t,dp);
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i];
    for(int d=n-1;d>=1;d--)
        for(int i=1;i<=n;i++)
        {
            int j=i+d;
            if(j>n)
                break;
            t=a[i]+a[j];
            val=(1+query1(n,dp2)+M-query1(j,dp2)+M-(query1(j,dp1)))%M;
            rez=(rez+val)%M;
            val=val;
            update1(j,dp2);
            update1(i,dp1);
            val=M-val;
            update1(j,dp1);
        }
    fout<<rez;
}