guest

H. Guest

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