Fişierul intrare/ieşire:	calc.in, calc.out	Sursă	ONI 2016, clasa a 10-a
Autor	Gorea Claudiu-Cristian	Adăugată de	Tatomir Alex •atatomir
Timp execuţie pe test	0.05 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Calc

La un concurs de informatică participă 2∙N elevi împărţiţi în N echipe de câte 2 . Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în reţea. Laboratorul de informatică e mai special: are 2∙N calculatoare, distribuite pe două rânduri la distanţă de un metru între ele (vertical şi orizontal) şi N cabluri de reţea de lungime un metru. Concursul se desfăşoară pe mai multe zile şi nu există două zile de concurs cu aceeaşi configuraţie a reţelei.
Exemplu: pentru N=3 , cei 6 elevi au fost împărţiţi în 3 echipe, iar aranjarea reţelei în cele 3 zile de concurs este cea din figura alăturată.
Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configuraţiile folosite în zilele de concurs. Cablul orizontal se notează prin 0 , iar cel vertical prin 1 . Lucrând ordonat şi eficient, pentru cele trei zile el îşi va nota valorile: 001 , 100 , respectiv 111 . Se observă că o reprezentare de genul 000 , 010 , 011 , 101 nu poate fi realizată.

Cerinţă

Cunoscând N, să se determine:

1. Numărul de zile modulo 1 000 000 007 în care se desfăşoară concursul.
2. Configuraţiile laboratorului în ziua X-1 şi ziua X+1 , cunoscând configuraţia zilei X .

Date de intrare

Fişierul de intrare calc.in conţine pe prima linie un număr natural p . Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2 .
Pe linia a doua vom avea numărul natural N .
Pe linia a treia se va găsi un şir de N cifre binare, fără spaţii între ele, reprezentând configuraţia corectă realizată de administrator în ziua X .

Date de ieşire

Dacă valoarea lui p este 1, se va rezolva numai punctul 1) din cerinţă. În acest caz, în fişierul de ieşire calc.out se va scrie un singur număr natural Z reprezentând numărul de zile în care se desfăşoară concursul pentru cele N echipe.
Dacă valoarea lui p este 2, se va rezolva numai punctul 2) din cerinţă. În acest caz, fişierul de ieşire calc.out va conţine două linii. Pe prima linie se vor scrie N cifre binare, fără spaţii între ele, reprezentând configuraţia reţelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spaţii între ele, reprezentând configuraţia din ziua următoare. Dacă în ziua precedentă nu există o configuraţie conform cerinţelor problemei, se va scrie pe prima linie valoarea -1 . Dacă în ziua următoare nu există o configuraţie conform cerinţelor problemei, se va scrie pe a doua linie valoarea -1 .

Restricţii

• 1 ≤ N ≤ 100000
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerinţa a doua se acordă 80 de puncte.

Exemplu

Cum se trimit solutii?