==Include(page="template/taskheader" task_id="bombar")==

==Include(page="template/raw")==

În timpul bombardamentelor, Paftenie a devenit genist. Trebuie să dezamorseze nişte bombe aflate adânc în pământ şi asta repede. Sunt exact $2*N$ bombe, aşezate în două rânduri paralele, ca în figura următoare:

In timpul bombardamentelor, Paftenie a devenit genist. Trebuie sa dezamorseze niste bombe aflate adanc in pamant si asta repede. Sunt exact $2*N$ bombe, asezate in doua randuri paralele, ca in figura urmatoare:

!problema/bombar?bombar0.png!

==html|<pre>O--O--O..O<br>I&nbsp; I&nbsp; I&nbsp; I<br>O--O--O..O</pre>==

Între oricare două bombe consecutive din acelaşi rând sau o bombă şi corespunzătoarea sa din celălalt rând se poate săpa un tunel (bombele între care se pot săpa tuneluri apar legate în figură). Trebuie să le dezamorseze pe toate, una care una, săpând exact $2*N-1$ tuneluri şi trebuie sa poată circula intre oricare doua bombe numai prin tunelurile săpate. Înainte de a trece la treaba, Paftenie se întreabă în câte moduri se pot sapa tunelurile.

Intre oricare doua bombe consecutive din acelasi rand sau o bomba si corespunzatoarea sa din celalalt rand se poate sapa un tunel (bombele intre care se pot sapa tuneluri apar legate in figura). Trebuie sa le dezamorseze pe toate, una care una, sapand exact $2*N-1$ tuneluri si trebuie sa poata circula intre oricare doua bombe numai prin tunelurile sapate. Inainte de a trece la treaba, Paftenie se intreaba in cate moduri se pot sapa tunelurile.

h2. Cerinţă

h2. Cerinta
 
Ajutati-l sa afle pana nu e prea tarziu!

Ajutaţi-l să afle pâna nu e prea târziu!

h2. Date de Intrare

Pe prima linie a fisierului de intrare $bombar.in$ este dat numarul $N$ al bombelor de pe un sir.

Pe prima linie a fişierului de intrare $bombar.in$ este dat numărul $N$ al bombelor de pe un şir.

h2. Date de Iesire

h2. Date de Ieşire

Fisierul de iesire $bombar.out$ va contine pe prima linie un singur numar, reprezentand numarul de posibilitati in care se pot sapa tunelurile.

Fişierul de ieşire $bombar.out$ va conţine pe prima linie un singur număr, reprezentând numărul de posibilităţi în care se pot săpa tunelurile.

h2. Restrictii si precizari

h2. Restricţii şi precizări

* $1 ≤ N ≤ 20.000$
h2. Exemplu

table(example). |_. bombar.in |_. bombar.out |_. explicatie |
| 2 | 4 | Bombele sunt plasate astfel:
o--o
I  I
o--o
El poate sapa tunelurile in 4 feluri:
o--o o--o o--o o--o
I  I I  I I  I I  I
o--o o--o o--o o--o |

table(example). |_. bombar.in |_. bombar.out |
| 2 | 4 |
 
h3. Explicaţie
 
Bombele sunt plasate astfel:
 
!problema/bombar?bombar1.png!
 
Paftenie poate săpa tunelurile în 4 feluri:
 
!problema/bombar?bombar2.png!
 
table(example). |_. bombar.in |_. bombar.out |
|3 |15 |
 
==Include(page="template/taskfooter" task_id="bombar")==

|3 |15 | blah |
==Include(page="template/taskfooter" task_id="bombar")==

383