Sắp đến thứ năm, ngày mà trang luyencode tổ chức contest cho các homies ba miền để thử sức của bản thân. Nhưng do quá bận bịu với các công việc khác, anh Hiếu vẫn chưa kịp lựa chọn độ khó của ~n~ bài trong contest lần này. Tiêu chí lựa chọn đề của anh Hiếu lần này là không có bài nào có độ khó giống nhau. Vì thế, anh Hiếu mới thông báo cho ~n~ người trong team luyencode đề xuất cho mình một số ~m~ là độ khó tối đa và anh Hiếu sẽ chọn ra một độ khó là một số tự nhiên có giá trị từ ~1~ đến ~m~.

Yêu cầu: Hãy giúp anh Hiếu và chúng mình đếm xem có bao nhiêu cách chọn ~n~ bài với độ khó khác nhau. Chú ý: luôn tồn tại đáp án.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~ (~n \le 10^5~)
Dòng thứ i trong n dòng tiếp theo chứa số nguyên dương ~m_i~ (~m_i \le 10^6~)

Output

Kết quả là phần dư của đáp án thoả mãn yêu cầu đề bài chia cho ~10^9 + 7~

Sample

Input #1

2
1 4

Output #1

3

Input #2

3
3 3 2

Output #2

4

Hint

Ví dụ 1: Có ~3~ cách lần lượt là (~1, 2~); (~1,3~) và (~1,4~).

Ví dụ 2: Có ~4~ cách lần lượt là (~1, 3, 2~); (~2, 3, 1~); (~3, 1, 2~) và (~3, 2, 1~).