Alice là một giáo viên mới của trường, hôm nay cô sẽ tổ chức một trò chơi để làm quen với các học sinh của mình. Lớp học của cô có ~n~ học sinh, học sinh thứ ~i~ có giá trị ~a_i~. Giá trị của mỗi học sinh là khác nhau.

Alice sẽ chia lớp học thành ~2~ đội, đội ~A~ và đội ~B~, mỗi đội sẽ cần ít nhất một thành viên. Sau đó, mỗi đội sẽ được chọn một màu sắc có số hiệu trong khoảng từ ~1~ tới ~10^9~ sao cho số hiệu màu sắc được chọn sẽ nhỏ hơn hoặc bằng giá trị của tất cả thành viên trong đội. Hai cách chia được gọi là khác nhau nếu một học sinh thuộc một đội khác hoặc có một màu khác trong hai cách chia.

Hãy giúp Alice đếm số cách chia đội khác nhau cho trò chơi của mình. Vì số cách chia có thể rất lớn, in ra kết quả sau khi lấy modulo cho ~10^9 + 7~.

Input

• Dòng thứ nhất gồm một số nguyên dương ~n~ ~(3 \le n \le 10^5)~

• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le 10^9)~

Output

• Dòng 1: Ghi ra một số duy nhất là kết quả của bài toán sau khi lấy modulo ~10^9 + 7~.

Scoring

Sample Input 1

2
1 2

Sample Output 1

4

Sample Input 2

2
2 3

Sample Output 2

12

Sample Input 3

8
9972 4343 8277 6198 7155 7123 8412 5555

Sample Output 3

818232006