How many are increasing?#5893

How many are increasing?

1 second

64 megabytes

Very easy

Given a sequence of $N$ integers, your task is to determine the number of strictly increasing subsequences within this sequence. The result should be presented modulo $1000007$ .

Input

The first line of the input contains the integer $N$ . The second line contains $N$ integers, which are the elements of the sequence, separated by spaces. Here, $0 < N \leq 11000$ 0 < N \le 11000, and each integer in the sequence does not exceed $1 0^{5}$ 10^5 in absolute value.

Output

Output a single line with the answer to the problem.

Examples

Example 1