Problem Description
Given a sequence A of N integers, find the number of strictly increasing subsequences, modulo 109 + 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 109 + 7.
Limits
Subtask 1 (30%): 1 ≤ N ≤ 103, 1 ≤ Ai ≤ 103.
Subtask 2 (10%): 1 ≤ N ≤ 106, Ai = i + 1. (A will be 1...N)
Subtask 3 (24%): 1 ≤ N ≤ 106, 1 ≤ Ai ≤ 106.
Subtask 4 (36%): 1 ≤ N ≤ 106, 1 ≤ Ai ≤ 109.
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