Soluții trimise

În clasa lui Ionuț sunt N elevi numerotați cu numere naturale de la 1 la N așezați în ordinea din catalog. Fiecare elev i (1 ≤ i ≤ N ) are ceea ce se numește un coeficient de popularitate \(A_i\) , un număr natural nenul. Fiecare elev din clasă are un grup de simpatizanți. Grupul de simpatizanți ai elevului i, notat cu \(G_i\) este reprezentat de cea mai lungă secvență de elevi din șirul dat în catalog, care îl conține pe elevul i, astfel încât coeficientul de popularitate al fiecărui elev j din secvență, \(A_j\) , să fie divizor al lui \(A_i\) . Lungimea secvenței, deci numărul elevilor din grupul de simpatizanți ai lui i, se notează cu \(|G_𝑖|\). Evident, elevul i face parte din propriul său grup de simpatizanți. Dacă elevul i face parte din grupul de simpatizanți ai elevului j, atunci nu este neapărat necesar ca și j să facă parte din grupul de simpatizanți ai elevului i.

După ore, unii elevi își invită la cofetărie grupul de simpatizanți, pentru câte o înghețată. Pentru un grup de simpatizanți \(G_i\) , elevul i merge și îi cere vânzătoarei exact \(|G_i|\) înghețate, dar vânzătoarea are o fire năstrușnică și îi spune că este disponibil doar un anumit număr de arome k, mereu cel mult egal cu numărul de înghețate cerute (\(1 ≤ 𝑘 ≤ |G_𝑖|\)). Elevii, creativi, calculează numărul de moduri în care se poate cumpăra înghețată pentru grup, astfel încât să achiziționeze fiecare sortiment cel puțin o dată; pentru grupul \(G_i\) , acest număr se notează cu \(v_i(k)\).

1. Determinați numărul de ordine din catalog al elevului care are cel mai numeros grup de simpatizanți. Se garantează că există un singur astfel de elev.
2. Lui Ionuț îi place foarte mult să analizeze vânzările magazinelor de înghețată și vă lansează Q întrebări de tipul: (i, st, dr) (cu \(1 ≤ i ≤ N\) și \(1 ≤ st ≤ dr ≤ |G_i|\)); pentru fiecare determinați valoarea expresiei: \(v_i(st) + v_i(st + 1) + \cdots + v_i(dr)\); cum valoarea poate fi foarte mare, luați în considerare restul împărțirii ei la \(10^9 + 7\).