THỰC HÀNH

Chính phủ Việt Nam có kế hoạch đến năm 2050 sẽ quản lý công dân Việt Nam bằng mã số cá nhân (Person ID). Mỗi người sẽ được cấp một mã số cá nhân (ID) phân biệt (không có hai công dân được cấp cùng một ID). Để đảm bảo quền tự do lựa chọn mã số cá nhân cho mình, chính phủ cho phép mỗi người sẽ chọn một số m và chính phủ sẽ xem xét cấp cho họ một ID là một số dương không lớn hơn m. Chính phủ muốn bạn đếm xem có bao nhiêu cách cấp ID cho n công dân?

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương n là số công dân cần cấp ID.
• Dòng thứ hai chứa n số nguyên dương phân biệt m₁, m₂, …, m_n, công dân thứ i muốn cấp ID nằm trong đoạn [1..m_i], hai số liên tiếp được ghi cách nhau mộ dấu cách.

Dữ liệu ra:

            Một số nguyên duy nhất là phần dư của số cách cấp ID khi chia cho số nguyên tố đầu tiên lớn hơn 10⁹.

Ví dụ:

Dữ liệu vào:
2
1 3

Dữ liệu ra:
2

Dữ liệu vào:
4
4 4 4 4

Dữ liệu ra:
24

Giải thích:

Trong test 1: Có 2 cách cấp mã số là { 1, 2 } hoặc { 1, 3 }.

Trong test 2: Số cách cấp mã số là số hoán vị của tập (1, 2, 3, 4).

Giới hạn: 1 ≤ n ≤ 10⁵; 1 ≤ m_i ≤ 10⁹.