Soluții trimise

Kida vă oferă două numere N și M. Ea vă mai oferă și un șir, A, de N numere naturale cuprinse între 0 și M inclusiv. Șirul A conține două tipuri de valori: valori cuprinse între 1 și M, care nu pot fi schimbate, respectiv valori de 0, care pot fi înlocuite cu orice număr cuprins între 1 și M. Pentru un șir V, cu valori între 1 și M, vom nota cu count(V) numărul de perechi (V[i], V[j]) de pe pozițiile i și j astfel încât i < j și cmmdc(V[i], V[j]) = 1. Se cere suma count(V) pentru toate șirurile distincte V care se pot obține din șirul A, înlocuind toate valorile de 0 cu numere cuprinse între 1 și M. Deoarece acest număr poate să fie foarte mare, se cere restul împărțirii sale la 1.000.000.009.