How many are increasing?

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 ≤ 11000, and each integer in the sequence does not exceed 10^5 in absolute value.

Output

Output a single line with the answer to the problem.

Examples