Fişierul intrare/ieşire:	rick.in, rick.out	Sursă	InfoOltenia 2018 - Clasa a 10-a
Autor	Bogdan Iordache	Adăugată de	Info-Oltenia 2018 •infooltenia
Timp execuţie pe test	1 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Rick

După succesul avut cu melodia “Get Schwifty!”, Rick a început să considere posibilitatea unei cariere în muzică. De-a lungul călătoriilor sale inter-dimensionale a strâns o colecţie impresionantă de N sunete. Fiecare sunet este descris prin frecvenţa sa, măsurată în BPM (beats per minute).

Rick a inventat un dispozitiv care, având la dispoziţie o mulţime de N sunete, alege aleator şi cu probabilitate uniformă o submulţime a acestei mulţimi. Sunetele acestei submulţimi sunt combinate, rezultând o melodie. Calitatea unei melodii este dată de cel mai mare divizor comun al frecvenţelor sunetelor combinate. Rick nu este niciodată mulţumit de melodia obţinută aşa că mereu resetează dispozitivul pentru a obţine alte melodii.

Cerinţă

Pentru a nu pierde o eternitate căutând melodia perfectă, Rick vă roagă pe voi să calculaţi media aritmetică a calităţii melodiilor generate de dispozitiv dupa un număr foarte mare (infinit) de selecţii de submulţimi de sunete. Cu alte cuvinte, care este valoarea medie (expected value) a calităţii unei melodii generate de dispozitiv?

Date de intrare

Prima linie a fişierului rick.in va conţine numărul natural N, cu semnificaţia din enunţ.
A doua linie va conţine N numere naturale, reprezentând frecvenţele sunetelor din colecţia lui Rick.

Date de ieşire

În fişierul rick.out afişaţi pe prima linie un număr natural X < 1.000.000.007. Dacă răspunsul este un număr raţional U/V, atunci X are proprietatea X∙V ≡ U (mod 1.000.000.007). Cu alte cuvinte, X∙V si U dau acelaşi rest la împărţirea cu 1.000.000.007.

Restricţii

• 1 ≤ N ≤ 500.000
• 1 ≤ frecvenţele sunetelor ≤ 500.000
• pentru 15% din punctaj 1 ≤ N ≤ 20
• pentru alte 25% din punctaj 1 ≤ N, diferenţa în modul dintre oricare două frecvenţe ≤ 1.000
• pentru alte 35% din punctaj 1 ≤ N, frecvenţele sunetelor ≤ 100.000
• prin probabilitate uniformă înţelegem că orice submulţime are aceeaşi probabilitate să fie extrasă de către dispozitiv
• considerăm că submulţimea vidă are cel mai mare divizor comun 1

Exemplu

Explicaţie

Avem 8 submulţimi posibile. Calculând cel mai mare divizor comun al elementelor fiecărei submulţimi, obţinem valorile: 1, 2, 6, 4, 2, 2, 2, 2.
Valoarea medie a calitaţii unei melodii este 21/8. 625000007∙8 şi 21 dau acelaşi rest la împărţirea cu 1.000.000.007.

Cum se trimit solutii?