CSES - Increasing Subsequence II
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Given an array of nn integers, your task is to calculate the number of increasing subsequences it contains. If two subsequences have the same values but in different positions in the array, they are counted separately.

Input

The first input line has an integer nn: the size of the array.

The second line has nn integers x1,x2,,xnx_1,x_2,\dots,x_n: the contents of the array.

Output

Print one integer: the number of increasing subsequences modulo 109+710^9+7.

Constraints

  • 1n21051 \le n \le 2 \cdot 10^5
  • 1xi1091 \le x_i \le 10^9

Example

Input:

3
2 1 3

Output:

5

Explanation: The increasing subsequences are [2][2], [1][1], [3][3], [2,3][2,3] and [1,3][1,3].