olimps!

Korektas iekavu izteiksmes

ID: iekavas3
Grūtība: 3/5
Laika limits: 1

Uzdevums

Korektu iekavu izteiksmi definē šādi:

() ir korekta iekavu izteiksme;
ja A ir korekta iekavu izteiksme, tad (A) arī ir korekta iekavu izteiksme;
ja A un B ir korektas iekavu izteiksmes, tad AB arī ir korekta iekavu izteiksme.

Tā, piemēram, (()()) un ()()((())) ir korektas iekavu izteiksmes, bet )( un ()) -nav.
Uzrakstiet programmu, kas ievadītam naturālam skaitlim n nosaka cik ir dažādas korektas iekavu izteiksmes garumā n (n vērtība nepārsniedz 100)!

Ievaddati

Teksta faila iekavas3.in pirmajā rindā dota naturāla skaitļa n vērtība, n<=100.

Izvaddati

Teksta faila iekavas3.out vienīgajā rindā jāizvada viens skaitlis - dažādo korekto iekavu izteiksmju garumā n skaits.

Piemērs

iekavas3.in iekavas3.out

4

2

Atsauces

Uzdevums izmantots Latvijas 15.informātikas olimpiādes I (skolas) kārtā.