Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2021-09-01 22:26:14.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	pastile.in, pastile.out	Sursă	OSEPI Baraj Seniori 2
Autor	Bogdan Pop, Bogdan Sitaru	Adăugată de	Matteo Verzotti •Matteoalexandru
Timp execuţie pe test	0.25 sec	Limită de memorie	131072 kbytes
Scorul tău	N/A	Dificultate	N/A

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₁, ..., 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₁, ..., a_N şi b₁, ..., b_N vor fi considerate la fel dacă şi numai dacă $\frac{a_1}{b_1} = \ldots = \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 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₁ ... p_N, reprezentând numărul de pastile disponibile din cea de-a i-a nuanţă iniţială.

Date de ieşire

Î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.

Restricţii

Vom nota V_min = min(p₁, ..., p_N) şi V_max = max(p₁, ..., p_N).
1 ≤ N ≤ 200 000
1 ≤ V_min ≤ V_max ≤ 200 000

Punctare

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.