Fişierul intrare/ieşire:	calorifer.in, calorifer.out	Sursă	FMI No Stress 8
Autor	Livia Magureanu	Adăugată de	Livia Magureanu •livlivi
Timp execuţie pe test	0.25 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Calorifer

Se spune ca prietenii nu sunt prieteni pana nu beau o bere impreuna, nu rezolva o problema de info impreuna si nu isi distrug caloriferele unul altuia impreuna. Asa este si in cazul a doua personaje, le numim Xdarascu si Xcsi (pentru a le pastra anonimitatea). Xdarascu nu duce lipsa de bautura si prieteni, dar Xcsi, in schimb, tine foarte mult sa ii demonstreze prietenului sau cat de buni prieteni sunt, motiv pentru care acesta s-a hotarat sa ii distruga toate caloriferele din casa. Nu este nevoie de mult IQ si multe beri pentru un astfel de act. Cum inteligenta personajelor nu este o necunoscuta a acestei probleme, astfel s-a si intamplat.

Dragostea era deja la prima vedere. Xcsi il mangaia pe Xdarascu cu vorbe dulci: "Ce coincidenta, ti-am distrus caloriferul inca o data, nu ti se pare amuzant!?”, in timp ce Xdarascu isi dorea sa il sarute cu pumni in fata, nu chiar in fata, dar totusi in fata. Dragostea era deja mult prea aprinsa. Geloasa pe prietenia autentica dintre cei doi, printesa Mieunita repede a sarit sa le bage bete in roate. Aceasta i-a dat o problema de info lui Xcsi pentru a ii distrage atentia de la partenerul lui batut de soarta, ocazie perfecta pentru a il fermeca pe acesta.

Ajutati-l pe sarmanul Bi...Xcsi sa rezolve problema de info in timp ce Xdarascu nu are ce face cu viata lui si urca calorifere pe perete.

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⁹ + 7 pentru ca Xcsi nu poate procesa mai mult).

Aici interveniti voi pentru a restabili iubirea!

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⁹ + 7.

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⁹ + 7.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ x ≤ 10⁹, unde x este un numar dat de printesa
• primul si ultimul numar scris de printesa pe foaie se afla printre numerele date

Exemplu

Explicaţie

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

Cum se trimit solutii?