Đất nước C11 sắp tiến hành cấp ~ n ~ mã số khác nhau cho ~ n ~ người dân để tiện việc quản lí. Để việc cấp mã số mang tính dân chủ, mỗi người dân được quyền chọn một số ~ max ~ và chính quyền sẽ cấp cho người đó một mã số là một số tự nhiên có giá trị từ 1 đến ~ max ~. Nhiệm vụ của bạn là đếm xem có bao nhiêu cách cấp mã số khác nhau cho ~ n ~ người này.

Dữ liệu vào

• Dòng 1: Số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 10^5) ~.
• Dòng ~ i ~ trong ~ n ~ dòng tiếp theo ghi số nguyên dương ~ max_i ~ ~ (1 ≤max_i ≤ 10^9) ~.

Kết quả

Ghi một số nguyên cho biết số cách cấp mã số khác nhau. Kết quả được chia lấy dư cho ~10^9+7~

Ví dụ:

Input 1

2
1
3 

Output 1

2 

Input 2

4
4
4
4
4 

Output 2

24 

Giải thích:

• Ví dụ 1: Có 2 cách cấp mã số là { 1, 2 } hoặc { 1, 3 }.
• ** Ví dụ 2:** Số cách cấp mã số là số hoán vị của tập (1, 2, 3, 4).