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$.

* 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$.

* $1 ≤ N ≤ 50$
* $1 ≤ K ≤ 10^9^$

* $1 ≤ M ≤ 50.000$
* $-10^9^ ≤ A{~i~} ≤ 10^9^$
 
h2. Punctare
 
Evaluarea se va face pe $10$ teste, fiecare valorand cate $10$ puncte.
Primele $5$ teste au $K ≤ 50.000$.
Testele $1, 2, 6$ si $7$ au $M = 10^9^ + 7$.
Testele $3, 4, 8$ si $9$ au $M$ numar prim.

* $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 |

| 3 1 10000

| 3 1 9999

1 2 3
| 24
|

| 4 50000 1000000007

| 3 4 29
0 23 0
| 26
|
| 4 50000 49999

2 0 2 3

| ?

| 43310

|
h3. Explicaţie