import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; import java.util.TreeMap; import java.util.TreeSet; public class D { static long mod=(int)(1e9)+7; static int [] a; static int n; static int [][]mem; static long [] fac,inv; public static void main(String[] args)throws Throwable { MyScanner sc=new MyScanner(); PrintWriter pw=new PrintWriter(System.out); n=sc.nextInt(); a=new int [n]; fac=new long [n+1]; inv=new long [n+1]; fac[0]=1L; for(int i=1;i<=n;i++) fac[i]=(fac[i-1]*i)%mod; for(int i=0;i<=n;i++) inv[i]=inv(fac[i], mod); for(int i=0;i0 && a[i]a[j-1]){ int l=j-i+1; if(l>pre) break; ans=(ans+((fac[pre]*inv[pre-l])%mod)*dp(j+1, l))%mod; j++; } return mem [i][pre]=(int)ans; } public static long inv(long x,long mod){ long r,y; for(r=1,y=mod-2;y!=0;x=x*x%mod,y>>=1){ if((y&1)==1) r=r*x%mod; } return r; } static class MyScanner { BufferedReader br; StringTokenizer st; public MyScanner() {br = new BufferedReader(new InputStreamReader(System.in));} String next() {while (st == null || !st.hasMoreElements()) { try {st = new StringTokenizer(br.readLine());} catch (IOException e) {e.printStackTrace();}} return st.nextToken();} int nextInt() {return Integer.parseInt(next());} long nextLong() {return Long.parseLong(next());} double nextDouble() {return Double.parseDouble(next());} String nextLine(){String str = ""; try {str = br.readLine();} catch (IOException e) {e.printStackTrace();} return str;} } }