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 ≤ M ≤ 10^9^ + 7$
* $0 ≤ A{~i~} ≤ M$
* M este impar

* Pentru $50%$ din punctaj, $K ≤ 50.000$

* 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

1 2 3
| 24
|

| 3 4 29
0 23 0
| 26
|

| 4 50000 49999
2 0 2 3

| ?

| 43310

|
h3. Explicaţie