h2. Cerinta
Si pentru ca problema Mieunitei nu a fost inca povestita, voi aveti ocazia de a o afla dupa ce ati citit tot acest enunt inutil: Fie un numar natural nenul $N$. Asupra acestui numar se pot aplica doua tipuri de operatii: inmultire cu $3$ sau impartire cu $2$ (daca numarul se divide cu $2$).

Printesa isi alege un numar natural nenul $N$ asupra caruia aplica succesiv operatiile de mai sus, notand pe o foaie rezultatul obtinut in urma fiecarei operatii. Dintre aceste rezultate, ea alege $K$ (printre care primul si ultimul), le rearanjeaza si i le da lui Xcsi. Acesta trebuie sa descopere ordinea initiala a celor $K$ numere si in cate moduri putea printesa Mieunita sa obtina aceste numere (modulo $10^9^ + 7$ pentru ca Xcsi nu poate procesa mai mult).

Printesa isi alege un numar natural nenul $N$ asupra caruia aplica succesiv operatiile de mai sus, notand pe o foaie rezultatul obtinut in urma fiecarei operatii. Dintre aceste rezultate, ea alege $K$ (printre care primul si ultimul), le rearanjeaza si i le da lui Xcsi. Acesta trebuie sa descopere ordinea initiala a celor $K$ numere.

Aici interveniti voi pentru a restabili iubirea!
h2. Date de intrare

Fisierul de intrare $calorifer.in$ contine pe prima linie un numar natural $P$ (care poate fi $0$ sau $1$). Pe a doua linie se afla un numar natural nenul $K$ cu semnificatia din enunt. Pe urmatoare linie se gasesc $K$ numere naturale nenule, reprezentand numerele date de printesa Mieunita.
 
* pentru $P = 0$, trebuie aflata DOAR ordinea initiala a numerelor
* pentru $P = 1$, trebuie aflat DOAR numarul de moduri de a obtine acele numere modulo $10^9^ + 7$.

Fisierul de intrare $calorifer.in$ contine pe prima linie un numar natural $K$ cu semnificatia din enunt. Pe urmatoarea linie se gasesc $K$ numere naturale nenule, reprezentand numerele date de printesa Mieunita.

h2. Date de ieşire
Fisierul de iesire $calorifer.out$ va contine o singura linie cu:
* $-1$ daca numerele nu pot fi obtinute prin aplicarea operatiilor descrise

* pentru $P = 0$, $K$ numere, reprezentand numerele initiale ordonate
* pentru $P = 1$, un numar, reprezentand numarul de moduri modulo $10^9^ + 7$.

* $K$ numere, reprezentand numerele initiale ordonate

h2. Restricţii

* Primul si ultimul numar scris de printesa pe foaie se afla printre numerele date.

* Pentru teste in valoare de 70 de puncte, P = 0.
* Pentru teste in valoare de 30 de puncte, P = 1.
 

* Pentru teste in valoare de 10 de puncte, P = 0 si $1 ≤ K ≤ 10$.
* Pentru teste in valoare de 20 de puncte, P = 0 si $1 ≤ K ≤ 1.000$.
* Pentru teste in valoare de 10 de puncte, P = 1 si $1 ≤ K ≤ 20$.

5
40 80 30 15 60
|80 40 60 30 15 |

|1
5
40 80 30 15 60
|2 |

h3. Explicaţie