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

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

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.

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.

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

h2. Date de ieşire

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

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

h2. Restricţii
* $1 ≤ N ≤ 100.000$

* $1 ≤ x $le; 10^9^$, unde x este un numar dat de printesa
* primul si ultimul numar scris de printesa pe foaie se afla printre numerele date

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

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

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

|

| 1
  5
  40 80 30 15 60
| 2
 
 
|

h3. Explicaţie

...

Numere initiale puteau fi (in ordine): $80 40 20 60 30 15$ sau $80 40 120 60 30 15$.

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