== include(page="template/taskheader" task_id="subsiruri2") ==

Valerică are un şir cu **N** caractere. Fiind o persoană minimalistă, fiecare caracter din şir poate fi egal cu litera $a$ sau cu litera $b$. Valerică se întreabă acum în câte moduri poate distribui toate caracterele şirului iniţial astfel încât să rezulte două subşiruri identice. Astfel, notând cu **X** şi **Y** două subşiruri care ar rezulta în urma unei distribuţii posibile şi analizând unul câte unul toate caracterele  din şirul iniţial, în ordinea în care acestea apar în şir, Valerică va decide, pentru fiecare, dacă îl va introduce la sfârşitul subşirului **X** sau la sfârşitul subşirului **Y**. De exemplu, pentru şirul iniţial abab, Valerică poate introduce primul şi al doilea caracter în subşirul **X** iar al treilea şi al patrulea caracter în subşirul **Y**, obţinând astfel două subşiruri identice.

Valerică are un şir cu $N$ caractere. Fiind o persoană minimalistă, fiecare caracter din şir poate fi egal cu litera $a$ sau cu litera $b$. Valerică se întreabă acum în câte moduri poate distribui toate caracterele şirului iniţial astfel încât să rezulte două subşiruri identice. Astfel, notând cu $X$ şi $Y$ două subşiruri care ar rezulta în urma unei distribuţii posibile şi analizând unul câte unul toate caracterele  din şirul iniţial, în ordinea în care acestea apar în şir, Valerică va decide, pentru fiecare, dacă îl va introduce la sfârşitul subşirului $X$ sau la sfârşitul subşirului $Y$. De exemplu, pentru şirul iniţial abab, Valerică poate introduce primul şi al doilea caracter în subşirul $X$ iar al treilea şi al patrulea caracter în subşirul $Y$, obţinând astfel două subşiruri identice.

h2. Cerinţă

h2. Date de intrare

Pe prima linie a fişierului **subsiruri2.in** se află numărul natural **N** reprezentând numărul de caractere din şirul iniţial. Pe următoarea linie se află şirul format din **N** caractere din mulţimea ${a,b}$.

Pe prima linie a fişierului $subsiruri2.in$ se află numărul natural $N$ reprezentând numărul de caractere din şirul iniţial. Pe următoarea linie se află şirul format din $N$ caractere din mulţimea ${a,b}$.

h2. Date de ieşire

Fişierul de ieşire **subsiruri2.out** va conţine o singură linie pe care va fi scris numărul total de posibilităţi de a forma două subşiruri identice din şirul iniţial.

Fişierul de ieşire $subsiruri2.out$ va conţine o singură linie pe care va fi scris numărul total de posibilităţi de a forma două subşiruri identice din şirul iniţial.

h2. Restricţii

* $1 ≤ N ≤ 40$, N par

* $1 ≤ N ≤ 40$, $N$ par

* pentru $20%$ din teste $N ≤ 16$
h2. Exemplu

h3. Explicaţie

Prima posibilitate este să formăm subşirul **X** din primele două caractere şi subşirul **Y** din ultimele două caractere. A doua posibilitate este să formăm subşirul **X** din ultimele două caractere şi subşirul **Y** din primele două caractere.

Prima posibilitate este să formăm subşirul $X$ din primele două caractere şi subşirul $Y$ din ultimele două caractere. A doua posibilitate este să formăm subşirul $X$ din ultimele două caractere şi subşirul $Y$ din primele două caractere.

table(example). |_. subsiruri2.in |_. subsiruri2.out |
| 6

abaaa

abaaaa

| 0
|

7516