supersuma

Supersuma

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

Poveste şi cerinţă...

Se considera un sir $A$ de $N$ numere intregi. Operatia $Verde$ aplicata sirului $A$ se face in doi pasi:
 
* Pasul 1. Se construieste un sir de numere intregi $B$. Initial, sirul e vid. Se considera toate submultimile lui $A$, inclusiv multimea vida, se calculeaza suma fiecareia, si se adauga numarele respective in sirul $B$.
* Pasul 2. Se inlocuieste $A$ cu $B$. Apoi, $B$ devine din nou vid.
 
Se cere suma $modulo M$ a numerelor din sirul obtinut dupa ce operatia $Verde$ a fost aplicata de $K$ ori sirului $A$.

h2. Date de intrare

Fişierul de intrare $supersuma.in$ ...

Fişierul de intrare $supersuma.in$ contine, pe prima linie, numerele $N$, $K$ si $M$. Pe urmatoarea linie se afla numerele din care e format sirul $A$.

h2. Date de ieşire

În fişierul de ieşire $supersuma.out$ ...

În fişierul de ieşire $supersuma.out$ se va afla un singur numar, si anume cel cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50$
* $1 ≤ K ≤ 10^9^$
* $1 ≤ M ≤ 10^9^ + 7$
* $0 ≤ A{~i~} ≤ M$
* M este impar
* Pentru $20$ de puncte, $M = 10^9^+7$, $k = 1$
* Pentru alte $10$ puncte, $M = 10^9^+7$, $k = 2$
* Pentru alte $10$ puncte, $k = 2$
* Pentru alte $20$ de puncte, $M<=500$, $k<=50.000$
* Pentru alte $20$ de puncte, $M=10^9^+7$, $k<=50.000$
* Pentru restul de $20$ de puncte, $M<=10^9^+7$, $k<=10^9^$

h2. Exemplu
table(example). |_. supersuma.in |_. supersuma.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

| 3 1 9999
1 2 3
| 24
|
| 3 4 29
0 23 0
| 26
|
| 4 50000 49999
2 0 2 3
| 43310
|

h3. Explicaţie

...

In primul exemplu, sirul $A$ dupa operatia $Verde$ este $0 1 2 3 3 4 5 6$.

== include(page="template/taskfooter" task_id="supersuma") ==