parent

Pentru a construi expresii matematice, folosim in practica trei tipuri de paranteze: "(" si ")", "[" si "]", "{" si "}". Un sir de caractere (format doar din cele 6 paranteze de mai sus) este corect parantezat daca si numai daca parantezele sunt imbricate corect si, in plus:
- intre oricare doua paranteze rotunde aflate in corespondenta nu apar paranteze patrate sau acolade;
- intre oricare doua paranteze patrate aflate in corespondenta nu apar acolade.

Pentru rezolvitorii cu inclinatii matematice (ceilalti pot sari cu incredere peste aceasta descriere matematica plictisitoare), putem reformula conditia de parantezare corecta astfel: Fie s un sir de caractere format doar din cele 6 paranteze de mai sus. Notam cu a[i][c] numarul de caractere c aflate in prefixul de lungime i al lui s. s este o parantezare corecta daca si numai daca pentru orice 1<=i<=N:
- a[i]['('] - a[i][')'] >= 0 si a[i]['['] - a[i][']'] >= 0 si a[i]['{'] - a[i]['}'] >= 0
- (a[i]['('] - a[i][')'] > 0) ==> ((a[i]['['] - a[i][']'] = 0) si (a[i]['{'] - a[i]['}'] = 0))
- (a[i]['['] - a[i][']'] > 0) ==> (a[i]['{'] - a[i]['}'] = 0)

Un exemplu de sir corect parantezat este "[[]()]{}". Sirul "())(" nu este parantezat corect deoarece parantezele nu sunt imbricate corect. Sirul "([])" nu este parantezat corect deoarece [] apare in interiorul unor paranteze rotunde.

Cerinta
Sa se determine cate siruri de parantezari corecte de lungime N exista.

Date de intrare
Pe prima linie a fisierului parent.in se gaseste numarul natural N.

Date de iesire
Pe singura linie a fisierului parent.out afisati numarul calculat, modulo 9311.

Restrictii si precizari
2 <= N <= 5000, N par

Exemplu

Timp maxim de executie/test: 0.7 secunde

stud. Stefan Ciobaca
ENs Cachan, DPT Infomatique
stefan.ciobaca@gmail.com