Haplar#2755
Xala Lizzi hər gün müəyyən bir dərmandan yarım həb qəbul edir. O, içində həb olan bir şüşə ilə başlayır.
Birinci gün, o, təsadüfi bir həbi çıxarır, onu iki hissəyə ayırır, bir hissəsini qəbul edir və digər hissəni yenidən şüşəyə qoyur.
Sonrakı günlərdə isə, o, şüşədən təsadüfi bir parçanı (bu ya bütöv bir həb, ya da yarım həb ola bilər) çıxarır. Əgər çıxardığı yarım həbdirsə, onu qəbul edir. Əgər bütöv həbdirsə, bir hissəsini qəbul edir, digər yarısını yenə şüşəyə qoyur.
Bütün şüşəni neçə fərqli üsulla boşaltmaq olar? Şüşədən həb çıxarmaq ardıcıllığını günlük bir sətr ilə ifadə edirik; burada -ci simvol olur (əgər həmin gün bütöv həb çıxarılıbsa), olur (əgər həmin gün yarım həb çıxarılıbsa), (0 \leq i < 2N). Şüşəni boşaltmaq üçün neçə müxtəlif düzgün sətir mümkündür?
Girişdə ən çoxu test nümunəsinə aid məlumatlar olacaq. Hər bir test nümunəsi üçün girişdə bir sətrdə bir müsbət tam ədəd — əvvəlcə şüşədə olan həblərin sayı (N \leq 30) veriləcək. Girişin sonu ilə göstəriləcək.
Hər bir test nümunəsi üçün cavabı yeni sətrə yazın. Bu, şüşəni boşaltmağın mümkün olan fərqli üsullarının sayıdır.
Nümunə 1