== include(page="template/taskheader" task_id="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.

    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.

h2. 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?

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?

h2. Date de intrare

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

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

h2. Restricţii