Problem Pastile


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\)

Restricții și precizări

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⟩

General info

ID: 69

Upload: liviu

Input: Console Input

Memory limit: 128MB/128MB

Time limit: 0.3s

Author: Bogdan Sitaru, Bogdan-Petru Pop

Source: ONI 2021 Baraj 2 Seniori: Problema 1

Submissions

Special Submissions