Fişierul intrare/ieşire:	mugur.in, mugur.out	Sursă	CCEX 2009
Autor	Lucian Boca	Adăugată de	Marius Stroe •Marius
Timp execuţie pe test	0.2 sec	Limită de memorie	8290 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Mugur

Spunem că un şir P de paranteze rotunde constituie o parantezare corectă dacă P = Ø sau P = M₁M₂..M_K, adică este format prin concatenarea mugurilor M₁, M₂, .., 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₁ = (())() are doi muguri: M₁ = (()) şi M₂ = (). Şirul S₂ = (()()(())) are un singur mugure: M₁ = (()()(())).

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.

Date de intrare

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

Date de ieşire

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

Restricţii

• 1 ≤ K ≤ N ≤ 500

Exemplu

Explicaţie

Avem şirurile:

()(()())
()((()))
(())(())
((()))()
(()())()

Cum se trimit solutii?