mugur

Mugur

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

Poveste şi cerinţă...

Spunem că un şir $P$ de paranteze rotunde constituie o parantezare corectă dacă $P = Ø$ sau $P = M{~1~}M{~2~}..M{~K~}$, adică este format prin concatenarea mugurilor $M{~1~}$, $M{~2~}$, .., $M{~K~}$ $(K ≥ 1)$.
 
Spunem că un şir $M$ de paranteze rotunde este un mugure dacă $M = (P)$, adică este format prin încadrarea unei parantezări corecte $P$ între caracterele $($ şi $)$. Astfel, fiind dată o parantezare corectă, se poate spune din câţi muguri este alcătuită. Spre exemplu, parantezarea $S{~1~} = (())()$ are doi muguri: $M{~1~} = (())$ şi $M{~2~} = ()$. Şirul $S{~2~} = (()()(()))$ are un singur mugure: $M{~1~} = (()()(()))$.
 
h2. Cerinţă
 
Fiind curios din fire, Amadaeus se întreabă câte parantezări corecte cu $K$ muguri poate alcătui cu $N$ perechi de paranteze. Deoarece rezultatul poate fi un număr foarte mare, Amadaeus se mulţumeşte (de aceasta dată) cu restul acestui număr la împărţirea cu $123457$.

h2. Date de intrare

Fişierul de intrare $mugur.in$ ...

Fişierul de intrare $mugur.in$ conţine o singură linie cu numerele $N$ şi $K$.

h2. Date de ieşire

În fişierul de ieşire $mugur.out$ ...

În fişierul de ieşire $mugur.out$ se va găsi numărul cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ K ≤ N ≤ 500$

h2. Exemplu
table(example). |_. mugur.in |_. mugur.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4 2
| 5

|
h3. Explicaţie

...

Avem şirurile:
 
$()(()())$
$()((()))$
$(())(())$
$((()))()$
$(()())()$

== include(page="template/taskfooter" task_id="mugur") ==

3978