import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] m = new int[n];
        long sum = 0;
        int prev = 0;
        for(int m_i = 0; m_i < n; m_i++){
            m[m_i] = in.nextInt();
            
            if(m_i != 0 && m[m_i] < m[m_i-1]){
                sum += permute(prev,m_i);
                prev = m_i;
            }
        }
        if(prev != n-1) sum += permute(prev,n);
        System.out.println(sum);
    }
    public static long permute(int start, int end){
        long max = end-start;
        long big = 1000000004;
        long sum = 0;
        for(long i = 1; i <= max; i++){
            sum = (sum+expo(i,max-i))%big;
        }
        return sum;
    }
    public static long expo(long a, long b){
        long result = 1;

        while (b > 0){
            if (b%2==1){
                result *= a;
            }
            b /= 2;
            a *= a;
        }
        return result;
    }
}