Feladat

Volt nekünk egy szabályos zárójelsorozatunk, gömbölyű és szögletes zárójelekből: (,),[,]. Precízen most nem definiálom, hogy mi az a szabályos (ha valakinek kell, ott van az eredeti feladatleírásban), de pont az, amire gondolunk. Igen ám, csak valami elromlott a kódolásban, és az összes szögletes zárójel kicserélődött gömbölyű nyitóra: (. Tehát megkapjuk ezt a módosult sztringet, a kérdés pedig az, hogy hányféle lehetett az eredeti zárójelsorozat.

Például ha amit végül kaptunk az ez: ((((())), akkor az eredeti négyféle lehetett: []((())), ([](())), (([]())), ((([]))). Mivel a lehetőségek száma nagyon sok lehet, az eredményt csak modulo 1 000 000 009 kell kiírni.

input

Az első sorban egy páros szám áll: 2<=N<=30000, a zárójelek száma, míg a második sorban egy N-hosszú sztring, ( és ) karakterekből, az elromlott zárójelezés.

output

A kimenet egyetlen szám: a lehetőségek száma mod 1 000 000 009.

BalticOI 2012

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.