guest

H. Guest

== include(page="template/taskheader" task_id="guest") ==

Consateanul tau Dorel are un hotel, si, ca toti hotelierii, vrea sa isi maximizeze profitul. Hotelul sau poate fi vizualizat ca o insiruire de $N$ camere, unele pline, unele goale.

Consateanul tau Dorel are un hotel, si, ca toti hotelierii, vrea sa isi maximizeze profitul. Hotelul sau poate fi vizualizat ca o insiruire de $N$ camere, unele pline, unele goale, de la $1$ la $N$.

Viata hotelierului nu este totusi atat de simpla. Din cand in cand, el trebuie sa elibereze cate o camera pentru diverse motive (venirea unui VIP,

 sau poate dezinsectia). In cazul acesta, el muta omul din camera intr-o alta camera, apoi muta omul dintr-acea camera intr-o alta camera, si tot asa, pana muta un om intr-o camera goala (desigur, daca camera este deja goala, el nu are nimic de facut). Oamenii mutati clar nu le place acest procedeu, si astfel vor negocia o dezpagubire monetara pentru deranjul cauzat. Fiecare om este dotat cu un anume $skill de negociere$ natural pozitiv $S$, si cu el va putea negocia o dezpagubire de $S * x$ lire elvetiene daca este mutat cu $x$ camere la dreapta sau la stanga.
Dorel iti spune ca daca tu il ajuti sa prezica care ar fi dezpagubirea totala daca el ar fi fortat sa elibereze fiecare camera in parte, atunci iti va plati $10%$ din toate profiturile sale pe urmatoarea luna. Puteti sa il ajutati ?

 sau poate dezinsectia). In cazul acesta, el muta omul dintr-acea camera intr-o alta camera, apoi muta omul dintr-acea camera intr-o alta camera, si tot asa, pana muta un om intr-o camera goala. Desigur, daca camera este deja goala, el nu are nimic de facut. Oamenilor mutati clar nu le place acest procedeu, si astfel vor negocia o despagubire monetara pentru deranjul cauzat. Fiecare om este dotat cu un anume $skill de negociere$ natural pozitiv $S$, si cu el va putea negocia o despagubire de $S * x$ lire elvetiene daca este mutat cu $x$ camere la dreapta sau la stanga.
Dorel iti spune ca daca tu il ajuti sa prezica care ar fi despagubire totala daca el ar fi fortat sa elibereze fiecare camera in parte, atunci iti va plati $10%$ din toate profiturile sale pe urmatoarea luna. Poti sa-l ajuti ?

h2. Date de intrare

h2. Date de ieşire
În fişierul de ieşire $guest.out$ va contine $T$ randuri, raspunsurile pentru cele $T$ teste.

Raspunsul pentru un test se calculeaza astfel. Daca costul pentru a elibera cea de a $i$-a camera este $r{~i~}$, atunci raspunsul este $(r{~1~} * 29^n-1^ + r{~2~} * 29^n-2^ + ... + r{~n~} * 29^0^) mod 1 000 000 007$.

Raspunsul pentru un test se calculeaza astfel. Daca costul pentru a elibera cea de a $i$-a camera este $r{~i~}$, atunci raspunsul este $(r{~1~} * 29^n-1^ + r{~2~} * 29^n-2^ + ... + r{~n~} * 29^0^) mod 1 000 000 007$. Sugeram sa folositi urmatorul cod pentru a transforma sirul $r$ in raspunsul pe test:
 
== code(cpp) |
 
/* functia ia r ca un sir de long long-uri indexate de la 1, si pe n, si returneaza raspunsul */
long long calculate_raspuns(long long r[], int n){
    long long ret = 0;
    for(int i = 1; i <= n; ++i){
        ret = (29 * ret + r[i]) % 1000000007ll; }
    return ret; }
 
==

h2. Restricţii
* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 100 000$

* $1 ≤ x ≤ 1 000 000 000$
* Exista cel putin o camera libera pentru fiecare test.

h2. Exemplu