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

Poveste şi cerinţă...

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

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 .

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

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.

* $... ≤ ... ≤ ...$

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

| 1
3
001
| 3
|
| 2
3
001
| -1
100

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

|
h3. Explicaţie