nis

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

Compile Errors


							
Time Limit: 1.5 Seconds
Memory Limit: 1024MB
No. of ACs: 42
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 30
2 10
3 24
4 36
5 0