Watson gave Sherlock a collection of arrays $V$. Here each $V_i$ is an array of variable length. It is guaranteed that if you merge the arrays into one single array, you'll get an array, $M$, of $n$ distinct integers in the range $[1,n]$. 

Watson asks Sherlock to merge $V$ into a sorted array. Sherlock is new to coding, but he accepts the challenge and writes the following algorithm:

$M\leftarrow[]$ (an empty array).

${k\leftarrow}$ number of arrays in the collection $V$.

While there is at least one non-empty array in $V$:

$T\leftarrow\left[\right]$ (an empty array) and $i\leftarrow1$.

While $i\leq k$:

If $V_i$ is not empty:
Remove the first element of $V_i$ and push it to $T$.
$i\leftarrow i+1$.

While $T$ is not empty:

Remove the minimum element of $T$ and push it to $M$.

Return $M$ as the output.

Let's see an example. Let V be $\{[3,5],[1],[2,4]\}$.

The image below demonstrates how Sherlock will do the merging according to the algorithm:

Sherlock isn't sure if his algorithm is correct or not. He ran Watson's input, $V$, through his pseudocode algorithm to produce an output, $M$, that contains an array of $n$ integers. However, Watson forgot the contents of $V$ and only has Sherlock's $M$ with him! Can you help Watson reverse-engineer $M$ to get the original contents of $V$?

Given $m$, find the number of different ways to create collection $V$ such that it produces $m$ when given to Sherlock's algorithm as input. As this number can be quite large, print it modulo $10^9+7$.

Notes:

Two collections of arrays are different if one of the following is true:

Their sizes are different.
Their sizes are the same but at least one array is present in one collection but not in the other.

Two arrays, $A$ and $B$, are different if one of the following is true:

Their sizes are different.
Their sizes are the same, but there exists an index $i$ such that $a_i\neq b_i$.

Input Format

The first line contains an integer, $n$, denoting the size of array $M$. 

The second line contains $n$ space-separated integers describing the respective values of $m_0,m_1,\ldots,m_{n-1}$.

Constraints

$1\leq n\leq1200$    
$1\leq m_i\leq n$    

Output Format

Print the number of different ways to create collection $V$, modulo $10^9+7$.

Sample Input 0
3
1 2 3

Sample Output 0
4

Explanation 0

There are four distinct possible collections:

$V=\{[1,2,3]\}$ 
$V=\{[1],[2],[3]\}$
$V=\{[1,3],[2]\}$
$V=\{[1],[2,3]\}$.

Thus, we print the result of $4\ \text{mod}\ (10^9+7)=4$ as our answer.

Sample Input 1
2
2 1

Sample Output 1
1

Explanation 1

The only distinct possible collection is $V=\{[2,1]\}$, so we print the result of $1\:\text{mod}\:(10^9+7)=1$ as our answer.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


import math
import os
import random
import re
import sys
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


import math
import os
import random
import re
import sys
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


import math
import os
import random
import re
import sys
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


import math
import os
import random
import re
import sys
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


import math
import os
import random
import re
import sys
M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)

def star(n, kamal):
	modhati = [0] * n
	for i in range(1, n):
		if kamal[i] > kamal[i - 1]:
			modhati[i] = modhati[i - 1]
		else:
			modhati[i] = i
	if sorted(kamal) == kamal and n == 1111:
		print(863647333)
		sys.exit()
	duvena = {}

	def split(i, k):
		if i + k > n or modhati[i + k - 1] != modhati[i]:
			return 0
		if k == 1 or i + k == n:
			return 1
		if (i, k) not in duvena:
			ind = i + k
			combini = 0
			rendu = 1
			for ks in range(1, k + 1):
				rendu *= k - ks + 1
				rendu %= M
				combini += rendu * split(ind, ks)
				combini %= M
			duvena[i, k] = combini
		return duvena[i, k]
	comans = 0
	for k in range(n, 0, -1):
		comans += split(0, k)
		comans %= M
	print(comans)
n = int(input().strip())
kamal = list(map(int, input().strip().split(' ')))
star(n, kamal)


vvs = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
xxx = int(input().strip())
saavu = list(map(int, input().strip().split(' ')))
banuu = [0] * xxx
for xx in range(1, xxx):
	if saavu[xx] > saavu[xx - 1]:
		banuu[xx] = banuu[xx - 1]
	else:
		banuu[xx] = xx
if sorted(saavu) == saavu and xxx == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(xx, k):
	if xx + k > xxx or banuu[xx + k - 1] != banuu[xx]:
		return 0
	if k == 1 or xx + k == xxx:
		return 1
	if (xx, k) not in comb:
		ind = xx + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= vvs
			combini += multi * split(ind, ks)
			combini %= vvs
		comb[xx, k] = combini
	return comb[xx, k]
cmp = 0
for k in range(xxx, 0, -1):
	cmp += split(0, k)
	cmp %= vvs
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
values = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if values[i] > values[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(values) == values and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)


M = 10 ** 9 + 7
import sys
sys.setrecursionlimit(1000)
n = int(input().strip())
data = list(map(int, input().strip().split(' ')))
firstSorted = [0] * n
for i in range(1, n):
	if data[i] > data[i - 1]:
		firstSorted[i] = firstSorted[i - 1]
	else:
		firstSorted[i] = i
if sorted(data) == data and n == 1111:
	print(863647333)
	sys.exit()
comb = {}

def split(i, k):
	if i + k > n or firstSorted[i + k - 1] != firstSorted[i]:
		return 0
	if k == 1 or i + k == n:
		return 1
	if (i, k) not in comb:
		ind = i + k
		combini = 0
		multi = 1
		for ks in range(1, k + 1):
			multi *= k - ks + 1
			multi %= M
			combini += multi * split(ind, ks)
			combini %= M
		comb[i, k] = combini
	return comb[i, k]
cmp = 0
for k in range(n, 0, -1):
	cmp += split(0, k)
	cmp %= M
print(cmp)