== include(page="template/taskheader" task_id="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ă.
h2.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 .
!>problema/calc?example.jpeg!
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ă.
h2. 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$ .
h2. 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 .
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$ .
h2. 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 .
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$ .
h2. 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.
* $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.
h2. Exemplu
