Programming teacher Dmitry Olegovich is going to propose the following task for one of his tests for students:

You are given a tree T with n vertices, specified by its adjacency matrix a[1... n, 1... n]. What is the output of the following pseudocode?
    
    
      
    used[1 ... n] = {0, ..., 0};  
      
    procedure dfs(v):  
        print v;  
        used[v] = 1;  
        for i = 1, 2, ..., n:  
            if (a[v][i] == 1 and used[i] == 0):  
                dfs(i);  
      
    dfs(1);  
    

In order to simplify the test results checking procedure, Dmitry Olegovich decided to create a tree T such that the result is his favorite sequence b. On the other hand, Dmitry Olegovich doesn't want to provide students with same trees as input, otherwise they might cheat. That's why Dmitry Olegovich is trying to find out the number of different trees T such that the result of running the above pseudocode with T as input is exactly the sequence b. Can you help him?

Two trees with n vertices are called different if their adjacency matrices a1 and a2 are different, i. e. there exists a pair (i, j), such that 1 ≤ i, j ≤ n and a1[i][j] ≠ a2[i][j].

Input

The first line contains the positive integer n (1 ≤ n ≤ 500) — the length of sequence b. 

The second line contains n positive integers b1, b2, ..., bn (1 ≤ bi ≤ n). It is guaranteed that b is a permutation, or in other words, each of the numbers 1, 2, ..., n appears exactly once in the sequence b. Also it is guaranteed that b1 = 1.

Output

Output the number of trees satisfying the conditions above modulo 109 + 7.

Examples

Input

3
1 2 3


Output

2


Input

3
1 3 2


Output

1
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
import java.util.Queue;

public class Main {
    int n;
    int[] a = new int[N];
    long[][] dp = new long[N][N];
    long dfs(int l, int r){
        if(dp[l][r] != -1)return dp[l][r];
        if(l >= r)return dp[l][r] = 1;
        long ans = 0;
        for(int i = l+1; i <= r; i++)
            if(i == r || a[i + 1] > a[l + 1])
                ans = (dfs(l+1, i) * dfs(i, r)+ans)%mod;    
        return dp[l][r] = ans;
    }
    void work() {
        while(cin.hasNext()){
            n = cin.nextInt(); for(int i = 1; i <= n; i++)a[i] = cin.nextInt();
            for(int i = 1; i <= n; i++){
                for(int j = i; j <= n; j++)dp[i][j] = -1;
            }
            System.out.println(dfs(1, n));
        }
    }

    Main() {
        cin = new Scanner(System.in);
        out = new PrintWriter(System.out);
    }

    public static void main(String[] args) {
        Main e = new Main();
        e.work();
        out.close(); 
    }

    public Scanner cin;
    public static PrintWriter out;
    static int N = 505;
    static int M = 5005;
    DecimalFormat df=new DecimalFormat("0.0000");
    static int inf = (int) 1e9;
    static long inf64 = (long) 1e18;
    static double eps = 1e-8;
    static int mod = 1000000007 ;
/*
    class Edge{
        int from, to, nex;
        Edge(){}
        Edge(int from, int to, int nex){
            this.from = from;
            this.to = to;
            this.nex = nex;
        }
    }
    Edge[] edge = new Edge[M<<1];
    int[] head = new int[N];
    int edgenum;
    void init_edge(){for(int i = 0; i < N; i++)head[i] = -1; edgenum = 0;}
    void add(int u, int v){
        edge[edgenum] = new Edge(u, v, head[u]);
        head[u] = edgenum++;
    }/*
    int upper_bound(int[] A, int l, int r, int val) {// upper_bound(A+l,A+r,val)-A;
        int pos = r;
        r--;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (A[mid] <= val) {
                l = mid + 1;
            } else {
                pos = mid;
                r = mid - 1;
            }
        }
        return pos;
    }/**/

    int Pow(int x, int y) {
        int ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans *= x;
            y >>= 1;
            x = x * x;
        }
        return ans;
    }
    double Pow(double x, int y) {
        double ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans *= x;
            y >>= 1;
            x = x * x;
        }
        return ans;
    }
    int Pow_Mod(int x, int y, int mod) {
        int ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans *= x;
            ans %= mod;
            y >>= 1;
            x = x * x;
            x %= mod;
        }
        return ans;
    }

    long Pow(long x, long y) {
        long ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans *= x;
            y >>= 1;
            x = x * x;
        }
        return ans;
    }
    

    long Pow_Mod(long x, long y, long mod) {
        long ans = 1;
        while (y > 0) {
            if ((y & 1) > 0)
                ans *= x;
            ans %= mod;
            y >>= 1;
            x = x * x;
            x %= mod;
        }
        return ans;
    }

    int gcd(int x, int y){
        if(x>y){int tmp = x; x = y; y = tmp;}
        while(x>0){
            y %= x;
            int tmp = x; x = y; y = tmp;
        }
        return y;
    }
    int max(int x, int y) {
        return x > y ? x : y;
    }

    int min(int x, int y) {
        return x < y ? x : y;
    }

    double max(double x, double y) {
        return x > y ? x : y;
    }

    double min(double x, double y) {
        return x < y ? x : y;
    }

    long max(long x, long y) {
        return x > y ? x : y;
    }

    long min(long x, long y) {
        return x < y ? x : y;
    }

    int abs(int x) {
        return x > 0 ? x : -x;
    }

    double abs(double x) {
        return x > 0 ? x : -x;
    }

    long abs(long x) {
        return x > 0 ? x : -x;
    }

    boolean zero(double x) {
        return abs(x) < eps;
    }
}