Robert s-a plictisit de tricoul său alb, așa că s-a hotărât să îl coloreze în culoarea sa preferată, albastru. El a primit de la prietenul său, Georgian, mai multe pastile de N nuanțe diferite de albastru, având acum $p_i$ pastile din cea de-a i-a nuanță de albastru (pentru i de la 1 la N). Pentru a colora tricoul, Robert va pune tricoul în mașina de spălat alături de diverse pastile.

Plictisit de nuanțele obișnuite de albastru, el va crea o nouă nuanță luând $a_1, ... , a_N$ pastile ($a_i$ pastile din nuanța inițială i). Robert va lua cel puțin o pastilă din fiecare nuanță inițială, și cel mult $p_i$ pastile din nuanța i. De asemenea, el poate folosi doar un număr întreg de pastile din fiecare tip. Două nuanțe $a_1, ... , a_N$ și $b_1, ... , b_N$ vor fi considerate la fel dacă și numai dacă $\frac{a_1}{b_1} = ... = \frac{a_n}{b_n}$

Acum, Robert se întreabă câte nuanțe noi diferite de albastru poate crea. Știind că acest număr poate fi foarte mare, el se mulțumește și cu răspunsul modulo 1 000 000 007.

Date de intrare

Pe prima linie se găsește un număr întreg N, reprezentând numărul de nuanțe distincte.
Pe cea de-a doua linie se găsesc N numere întregi $p_1 ... p_N$ , reprezentând numărul de pastile disponibile din cea de-a i-a nuanță inițială.

Date de ieșire

Se va afișa o singură linie, ce conține un singur număr întreg, reprezentând numărul de nuanțe diferite ce se pot forma modulo 1 000 000 007.

Restricții și precizări

• Vom nota $V_{min} = min(p_1, ... , p_N)$ și $V_{max} = max(p_1, ... , p_N)$.
• 1 ≤ N ≤ 200 000
• $1 ≤ V_{min} ≤ V_{max} ≤ 200 \ 000$

Subtask 1 (2 puncte)

• $V_{min} = 1$

Subtask 2 (6 puncte)

• $1 ≤ N, V_{max} ≤ 7$

Subtask 3 (4 puncte)

• $1 ≤ N, V_{max} ≤ 8$

Subtask 4 (16 puncte)

• $1 ≤ N, V_{max} ≤ 100$

Subtask 5 (11 puncte)

• $1 ≤ N, V_{max} ≤ 1 \ 000$

Subtask 6 (7 puncte)

• $1 ≤ N, V_{max} ≤ 5 \ 000$

Subtask 7 (15 puncte)

• $1 ≤ N, V_{max} ≤ 30 \ 000$

Subtask 8 (10 puncte)

• $V_{min} = V_{max}$

Subtask 9 (8 puncte)

• $1 ≤ V_{min} ≤ 100$

Subtask 10 (21 puncte)

• Fără restricții suplimentare.

Exemple

stdin

3
2 3 2

stdout

11

stdin

4
7 7 7 7

stdout

2303

stdin

7
15 8 19 7 15 8 19

stdout

36191027

stdin

2
31124 150719

stdout

851838928

Explicații

Pentru primul exemplu, cele 11 nuanțe posibile sunt:

• ⟨1, 1, 1⟩ (la fel cu ⟨2, 2, 2⟩ )
• ⟨1, 1, 2⟩
• ⟨1, 2, 1⟩
• ⟨1, 2, 2⟩
• ⟨1, 3, 1⟩
• ⟨1, 3, 2⟩
• ⟨2, 1, 1⟩
• ⟨2, 1, 2⟩
• ⟨2, 2, 1⟩
• ⟨2, 3, 1⟩
• ⟨2, 3, 2⟩