== include(page="template/taskheader" task_id="pastile") ==
Poveste şi cerinţă...
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ă <tex>\frac{a_1}{b_1} = \ldots = \frac{a_N}{b_N}</tex>.
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*.
h2. Date de intrare
Fişierul de intrare $pastile.in$ ...
Pe prima linie a fişierului de intrare $pastile.in$ 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ă.
h2. Date de ieşire
În fişierul de ieşire $pastile.out$ ...
În fişierul de ieşire $pastile.out$ 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*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 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$
h2. Punctare
table(example). |_. Subtask |_. Punctaj |_. Restricţii |
| 1 | 2 | V{~min~} = 1 |
| 2 | 6 | 1 ≤ N, V{~max~} ≤ 7 |
| 3 | 4 | 1 ≤ N, V{~max~} ≤ 8 |
| 4 | 16 | 1 ≤ N, V{~max~} ≤ 100 |
| 5 | 11 | 1 ≤ N, V{~max~} ≤ 1 000 |
| 6 | 7 | 1 ≤ N, V{~max~} ≤ 5 000 |
| 7 | 15 | 1 ≤ N, V{~max~} ≤ 30 000 |
| 8 | 10 | V{~min~} = V{~max~} |
| 9 | 8 | 1 ≤ V{~min~} ≤ 100 |
| 10 | 21 | Fără restricţii suplimentare. |
h2. Exemplu
table(example). |_. pastile.in |_. pastile.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3
2 3 2
| 11 |
| 4
7 7 7 7
| 2303 |
| 7
15 8 19 7 15 8 19
| 36191027 |
| 2
31124 150719
| 851838928 |
h3. Explicaţie
...
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)$
== include(page="template/taskfooter" task_id="pastile") ==
