#include <fstream>
#include<algorithm>
using namespace std;
ifstream cin ("psir.in");
ofstream cout ("psir.out");
long long n,best[2010][2010],data[100010],sum,t,sol,k=1;
struct bla
{
    long long  o,v;
} date[2010];
bool sortare (bla q,bla w)
{
    return q.v<w.v;
}
void read ()
{
    cin>>n; for(int i=1;i<=32;i++) k*=2;
    for(int i=1;i<=n;i++)
        cin>>date[i].v,date[i].o=i,data[i]=date[i].v;
        sort(date+1,date+n+1,sortare);
}
void big (int ord,long long value)
{
    int st=1,dr=n,mij=(st+dr)/2;
    while(st<=dr)
    {
        if(date[mij].v>value) dr=mij-1;
        else st=mij+1;
        mij=(st+dr)/2;
    }
    long long h=best[ord][n]-best[ord][dr];
    if(h<0) h+=t; h%=k;
    if(t==0)
    sum=sum+h;
    else if(t==1) { if(date[dr].v==value) dr--; sum=sum+best[ord][dr];}  sum%=k;
}
void solve ()
{
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(date[j].o<i)
            {    sum=1;
                if(date[j].v<data[i]) t=0; else if(date[j].v>data[i]) t=1; else t=-1;
                big(date[j].o,data[i]);
                best[i][j]=best[i][j-1]+sum; sol+=sum; sol%=k; best[i][j]%=k;
            } else best[i][j]=best[i][j-1];
        }
    }
    cout<<sol;
}
int main()
{
    read();
    solve();
    cin.close();
    cout.close();
    return 0;
}