#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 1e5+;

long long n;

long long a[maxn];

long long b[maxn];

long long c[maxn];

long long mod = 1e9+;

void add(long long c[],long long i,long long j);

long long getsum(long long c[],long long i);

int main()

{

    int i,j,k;

    while(scanf("%lld",&n) != EOF)

    {

        memset(c, , sizeof(c));

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

        {

            scanf("%lld",a+i);

            b[i] = a[i];

        }

        sort(b+,b+n+);

        long long sum = ;

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

        {

            long long ans=;

            long long pos=lower_bound(b+,b+n+,a[i]) - b;

            ans = getsum(c,pos);

            sum += ans+;

            sum %= mod;

            add(c, pos, ans+);

        }

        printf("%lld\n",sum);

    }

}

long long lowbit(long long k)

{

    return k&(-k);

}

void add(long long c[],long long i,long long j)

{

    while(i<=n)

    {

        c[i] += j;

        c[i] %= mod;

        i += lowbit(i);

    }

}

long long getsum(long long c[],long long i)

{

    long long sum = ;

    while(i > )

    {

        sum += c[i];

        sum %= mod;

        i -= lowbit(i);

    }

    return sum;

}