Laiko ribojimas: 1s

Atminties ribojimas: 32MB

Duomenų failas: obelynas.in

Rezultatų failas: obelynas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Obelynas

Neseniai Adomas pradėjo ūkininkauti ir jam tas sekasi ganėtinai neblogai. Šiuo metu jo sode auga kopūstai, morkos bei dar daug kitų gėrybių.

Siekdamas praplėsti savo sodo asortimentą, Adomas taip pat nusprendė auginti obelis. Tam, kad jo sodas atrodytų kiek įmanoma gražiau ir išskirtiniau, jis sumanė pasodinti kuo daugiau skirtingų obelų. Būdamas geras matematikas, jis į visas savo obelis žiūri kaip į dvejetainius medžius, kurių visi turi tokį patį viršūnių skaičių (visos obelys yra tos pačios veislės). Medelius jis taip pat sunumeravo nuo 1 iki N ir kiekvienam priskyrė kodą, leidžiantį lengvai atpažinti medį, t.y. kiekvieną medį Adomas koduoja apeidamas jį inorder tvarka ir žymėdamas lapus 0, o kitas viršūnes 1. Pavyzdžiui, medį:

    *
   / \
  *   *
 / \
*   *

galima užrašyti kaip skaičių seką: 01010

Šiuo kodus Adomas surašė ant popieriaus lakštų ir atitinkama tvarka (viršuje 1 obels kodas, o apačioje N'tosios obels).

Deja, vieną naktį į jo namus įsilaužė plėšikai. Šie plėšikai, norėdami sugadinti gražųjį Adomo obelyną (turbūt šie plėšikai buvo Adomo konkurentai), paėmė ir pavogė dalį lapų su obelų aprašais. Likusią dalį išmaišė ir, kad būtų sunkiau atkurti pirmąją seką, dar papildomai pridėjo savo aprašų.

Tad Adomas norėtų jūsų paprašyti pagelbėti atsekant, kurie iš likusių aprašų kokias obelis atitinka. Tiksliau, ne! Adomas pastebėjo, kad tą patį kodą gali atitikti keletas medžių, t.y. kodą 01010 taip pat atitinka medis:

  *
 / \
*   *
   / \
  *   *

Tad atrodo, kad plėšikai padarė neatitaisomą žalą. Tačiau išlieka vienas įdomus klausimas: kiek dvejetainių medžių išties gali atitikti kiekvieną iš nurodytų kodų. Šį skaičių jums ir reikės rasti.

Pradiniai duomenys

Pirmojoje pradinių duomenų eilutėje bus nurodytas skaičius N (0\\leqN\\leq100), nurodantis likusių lakštų kiekį. Likusiose N bus nurodytas dvejetainio medžio (kurio viršūnių kiekis nėra didesnis už 100) kodas.

Rezultatai

Reikia išvesti N eilučių. Kiekvienoje iš eilučių reikia nurodyti kiek dvejetainių medžių atitinka atitinkamą pradiniuose duomenyse nurodytą kodą moduliu 1000001.

Pavyzdžiai

Pradiniai duomenys Rezultatai 
5
010
1
0
01010
0110010
 
1
0
1
2
0

Inorder apėjimas

funkcija apeiti(viršūnė v)
    jei v yra lapas
        atspausdinti 0
        baigti darbą
    kviesti apeiti(v kairysis sūnus)
    atspausdinti 1
    kviesti apeiti(v dešinysis sūnus)