• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

گاوچرانان جوان و بی‌ادعای قبیله‌، هر هفته جلساتی را با محوریتِ بحث و تبادل نظر پیرامون مِتُدها و راهکارهای نوین گاوچرانی برگزار می‌کنند. این جلسات یک مامور ورود و خروج دارد که چهارچشمی، چشمانش را به در دوخته تا ورود و خروج همه‌ی افراد را بدون هیچ کم و کاستی ثبت کند.

این مامور با ورود هر نفر به جلسه، کاراکتر I و با خروج هر نفر از جلسه، کاراکتر O را در برگه‌ی ثبت ورود و خروجش می‌نویسد. بدین ترتیب به ازای هر جلسه، مامور ثبت یک رشته متشکل از I و O را در پایان کار تحویل رئیس جلسه می‌دهد.

متاسفانه در آخرین جلسه‌ای که همین جمعه‌ی هفته‌ی پیش برگزار شد، در اواسط جلسه بود که مامورِ ثبت ورود و خروج خوابش می‌برد و از یک‌جایی به بعد، ورود و خروج افراد را ثبت نمی‌کند! او اکنون متوجه اشتباهش شده و می‌خواهد به‌گونه‌ای، این اشتباه خودش را ماسمالی کند :))

او فرض می‌کند طول رشته‌ای که می‌بایست در پایان جلسه تحویلِ رئیس می‌داده، $2n$ بوده و اکنون با این فرض می‌خواهد بداند تا به چند روش مختلف می‌تواند باقیِ رشته‌اش را تکمیل کند. به او در پیدا کردن این تعداد کمک می‌کنید؟

ورودی

در سطر اول ورودی، تنها یک عدد طبیعی $n$ می‌آید. قول می‌دهیم که $n$ کمتر یا مساوی ۲۰ است. در خط دوم رشته‌ای که مامور ثبت تا قبل از خوابیدن نوشته، داده می‌شود.

خروجی

تعداد روش‌هایی را که مامور ثبت ورود و خروج می‌تواند باقی رشته را تکمیل کند، به دست آورید.

مثال

ورودی نمونه ۱

1
I

خروجی نمونه ۱

1

• توضیح: در این‌جا، رشته‌ی نهایی ما باید به طول دو باشد. تنها راه پرکردن باقی رشته، گذاشتن یک O بعد از I است.

ورودی نمونه ۲

3
II

خروجی نمونه ۲

3

• توضیح: راه‌های پر کردن باقی رشته، IIIOOO و IIOIOO و IIOOIO است.