Đấ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.

Input

• Dòng ~1~: Số nguyên dương ~N~.
• Dòng ~i~ trong ~N~ dòng tiếp theo: Số nguyên dương ~max_{i}~.

Output

• Phần dư khi chia số cách cấp mã số khác nhau cho ~k~. Với ~k~ là số nguyên tố nhỏ nhất lớn hơn ~10^{9}~.

Giới hạn

• ~1 \leq N \leq 10^{5}~.
• ~1 \leq max_{i} \leq 10^{9}~.

Sample Input 1

2
1
3

Sample Output 1

2

Sample Input 2

4
4
4
4
4

Sample Output 2

24

Note

- 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)~.