#include<cstdio>

 #include<algorithm>

 #define FFC(i,a,b) for(int i=a;i<=b;i++)

 #define LL long long

 using namespace std;

 LL tree[];

 int maxn,mod=,l,r,t,len,mid;

 int dt[],a[];

 void init(int n){maxn=n;for(int i=;i<=maxn;i++)tree[i]=;}

 inline void add(int x,int v){for(int i=x;i<=maxn;i+=i&-i)tree[i]=(tree[i]+v)%mod;}

 inline LL sum(int x){LL an=;for(;x>;x-=x&-x)an=(an+tree[x])%mod;return an;}

 inline int lowb(int x){for(l=,r=len;l<=r;)if(a[mid=(l+r)>>]>=x)r=(t=mid)-;else l=mid+;}

 int main(){

     int n;

     while(~scanf("%d",&n)){

         FFC(i,,n){

             scanf("%d",&dt[i]);

             a[i]=dt[i];//离散化数组

         }

         sort(a+,a++n);

         len=unique(a+,a++n)-a-;//离散化

         init(len);

         LL ans=;

         FFC(i,,n){

             lowb(dt[i]);//二分查找

             int tt=sum(t);

             add(t,tt+);

             ans=(ans+tt+)%mod;//注意，一个数它本身也是一个递增子列，所以要加一

         }

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

     }

     return ;

 }