nis

Problem Description

Given a sequence A of N integers, find the number of strictly increasing subsequences, modulo 10⁹ + 7.

Input

The first line of input will contain a single integer, N.

The second line of input will contain N integers, representing the sequence A.

Output

The output should contain one line with one integer, the number of strictly increasing subsequences, modulo 10⁹ + 7.

Limits

Subtask 1 (30%): 1 ≤ N ≤ 10³, 1 ≤ A_i ≤ 10³.

Subtask 2 (10%): 1 ≤ N ≤ 10⁶, A_i = i + 1. (A will be 1...N)

Subtask 3 (24%): 1 ≤ N ≤ 10⁶, 1 ≤ A_i ≤ 10⁶.

Subtask 4 (36%): 1 ≤ N ≤ 10⁶, 1 ≤ A_i ≤ 10⁹.

Subtask 5 (0%): Sample Testcases.

Sample Input 1

4
1 2 3 4

Sample Output 1

15

Sample Input 2

5
1 6 2 4 3

Sample Output 2

13