*Nguồn đề + test: * Free Contest (https://freecontest.net/),

* Đề gốc: * https://drive.google.com/file/d/15y5cnDohfBpU4AOM1QgwDZJnui_YPp6z/view

*Lời giải: * https://drive.google.com/file/d/161OduQZ7Pnaa6kjBuAZ-2xcn5hCsaYhE/view

Một dãy X độ dài x được gọi là dãy số phan xi păng nếu ~\forall{i}, 2 \leq i \leq x : X_{i-1} < X_{i}.~

Cho một dãy A có độ dài n. Một tập hợp B có b phần tử có giá trị nằm trong đoạn [1,n] được gọi là tập hợp phan xi păng nếu có thể thay đổi vị trí các phần tử của dãy sau ~A_{B_1}, A_{B_2}, A_{B_3},..., A_{B_b}~ sao cho dãy này trở thành dãy phan xi păng.

Tức là đếm số tập hợp B: gồm ~ 1 \leq b_i \leq n ~, sao cho từ tập hợp b ta có một dãy(là tập con của A) tương ứng ~A_{b_1}, A_{b_2}, A_{b_3},...~ thỏa mãn sao cho tồn tại 1 cách sắp xếp dãy này thành một dãy phan xi păng.

Vd dãy :

• A : 3 1 2 3 2

• Tập B có thể là {1,2} => A[1] = 3 , A[2] = 1 => ta có dãy 3,1 sắp xếp lại ta có dãy 1,3 là dãy phan xi păng

• Lưu ý {1,2} = {2,1} "tập hợp"

Hãy đếm số tập hợp B là tập hợp phan xi păng.

Input

• Dòng đầu tiên gồm một số nguyên N ~(1 \leq N \leq 10^5)~.
• Dòng tiếp theo chứa n số nguyên ~A_i~.

Output

• Kết quả bài toán, chia dư cho ~10^9 + 7~.

Sample Input 1

5
3 1 2 3 2

Sample Output 1

18

Giải thích

Các tập hợp thỏa mãn đó là {}, {1}, {2}, {3}, {4}, {5}, {1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {4,5}, {1,2,3}, {1,2,5}, {2,3,4}, {2,4,5}.

Task:

• Subtask 1 (60% số điểm) : ~n \leq 20~
• Subtask 2 (40% số điểm) : ~n \leq 2 . 10^5~