Cô Matcha 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 đánh mã số là a_i (i = 1, 2, …, n), mã số của các học sinh là khác nhau.

Cô Matcha muốn chia lớp học của mình 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ó giá trị trong khoảng từ 1 tới 10⁹ sao cho màu sắc đó nhỏ hơn hoặc bằng mã số của tất cả thành viên trong đội. Hai cách chia được gọi là khác nhau nếu ít nhất 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.

Yêu cầu: Hãy giúp cô Matcha đế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, cho biết kết quả sau khi lấy modulo cho 1e9 +7.

Dữ liệu vào:

• Dòng thứ nhất là số nguyên dương n (3 ≤ n ≤ 10⁵);

• Dòng thứ hai chứa n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁹ với i = 1, 2, …, n)

Kết quả: Ghi một số nguyên duy nhất là kết quả của bài toán sau khi lấy modulo cho 1e9 +7.

Ví dụ:

Giải thích: có 4 cách chia đội

• Cách 1: Đội A gồm học sinh 1 và có màu 1, đội B gồm học sinh 2 và có màu 1;

• Cách 2. Đội A gồm học sinh 1 và có màu 1, đội B gồm học sinh 2 và có màu 2;

• Cách 3. Đội A gồm học sinh 2 và có màu 1, đội B gồm học sinh 1 và có màu 1;

• Cách 4. Đội A gồm học sinh 2 và có màu 2, đội B gồm học sinh 1 và có màu 1.

Subtask:

• Trong tất cả mọi test: 3 ≤ n ≤ 10⁵ , 1 ≤ a_i ≤ 10⁹ (với i = 1, 2, …, n);

• Subtask 1: 40% số test có n ≤ 20;

• Subtask 2: 40% số test có n ≤ 30 và a_i ≤ n (với i = 1, 2, …, n);

• Subtask 3: 20% số test còn lại không có ràng buộc gì thêm.