Sequence Reduction Operation Schemes

You are given a sequence of length \(n\): \(a_1, a_2, \dots, a_n\). As long as the sequence is not non-decreasing (i.e. there exists an index \(i\) with \(a_i > a_{i+1}\)), you must remove one element from the sequence. This removal operation is repeated until the sequence becomes non-decreasing. Two operation schemes are considered different if they differ in the order or number of removals. Output the number of different removal schemes modulo \(10^9+7\).

Note: If the initial sequence is already non-decreasing then no removal is performed and the answer is 1.

Formal definition:

Define a function \(f(S)\) over a sequence \(S\) as follows: \[ f(S)=\begin{cases}1,& \text{if } S \text{ is non-decreasing},\\[8pt] \sum_{i=1}^{|S|} f(S\setminus\{S_i\}),& \text{otherwise.} \end{cases} \] The answer is \(f([a_1, a_2, \dots, a_n])\) modulo \(10^9+7\).

inputFormat

The first line contains an integer \(n\) (the number of elements in the sequence). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer representing the number of different removal schemes modulo \(10^9+7\).

sample

1
5

1