A bitonic subsequence is a sequence which is first non-decreasing and then non-increasing.

You are given an array of size N. You need to find the number of bitonic subsequences.

As the number can be very large, output it modulo 1e9 + 7.

Input

First line contains a single integer N, the size of array

The next line contains N integers, the elements of the array.

Output

Output number of bitonic subsequences modulo 1e9 + 7.

Constraints

1 ≤ N ≤ 100000, size of array

1 ≤ A[i] ≤ 109

Limits

Time: 2 second

Memory: 256 MB