Mô tả và yêu cầu

Đất nước C11 sắp tiến hành cấp 𝑛 mã số khác nhau cho 𝑛 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ố 𝑚𝑎𝑥 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 𝑚𝑎𝑥.
Nhiệm vụ của bạn là đếm xem có bao nhiêu cách cấp mã số khác nhau cho 𝑛 người này.
Dữ liệu vào:
+ Dòng 1: Số nguyên dương 𝑛 (1 ≤ 𝑛 ≤ 105).
+ Dòng 𝑖 trong 𝑛 dòng tiếp theo ghi số nguyên dương 𝑚𝑎𝑥𝑖 (1 ≤ 𝑚𝑎𝑥𝑖 < 109).
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 109 + 7

Ví dụ

Input            Output                Input            Output
                   2                2                     4                24
                   1                                      4
                   3                                      4
                                                          4
                                                          4
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).