• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۶۴ مگابایت

در آخرین اکتشافات باستان‌‌شناسان در سرزمین «کهن»، یک دفترچه بسیار مرموز پیدا شده است. طی تحقیقات بسیار مشخص شد که این دفترچه، دفترچه خاطرات رستم است. پس از ناکام ماندن تلاش باستان‌شناسان برای خواندن خاطرات رستم، مشخص شد که رستم از بیم خوانده شدن خاطراتش، متن این دفترچه را با الگوریتم‌های بسیار پیچیده رمزنگاری کرده است و کلید این رمز را در یکی از اهرام «دور» قرار داده است.

این کلید امروزه تحت تدابیر شدید امنیتی در موزه «دور باستان» نگهداری می‌شود و این موزه به هیچ وجه حاضر نیست این کلید را در اختیار باستان‌‌شناسان سرزمین «کهن» قرار دهد.

پس از اصرارهای زیاد باستان‌‌شناسان «کهن»، موزه «دور باستان» حاضر شد این کلید را در اختیار آن‌ها بگذارد. بنابراین درب سالن محل نگه‌داری این کلید را باز کرد تا بروند و این کلید را بردارند. اما باستان‌‌شناسان باهوش «کهن» متوجه شدند در مسیر درب سالن تا خود کلید تعدادی تله قرار داده شده است. آنها با تجهیزات پیشرفته‌ی خود، مکان این تله‌ها را پیدا کرده‌اند و اکنون می‌خواهند همه مسیر‌های ممکن برای رسیدن به کلید را بررسی کنند و بهترین مسیر را انتخاب کنند.

این سالن به شکل یک جدول $1\times n$ است که در خانه‌ی شماره ۱، باستان‌شناسان «کهن» قرار دارند (با نماد B) و در خانه‌ی شماره $n$، کلید قرار دارد (با نماد K) و در برخی از خانه‌های دیگر تله وجود دارد (با نماد T). اگر باستان‌شناسان وارد خانه‌ی تله‌دار بشوند، به پایین می‌افتند و خوراک کوسه‌ها می‌شوند.

باستان‌شناسان «کهن» در هر حرکت می‌توانند یکی از این سه کار را انجام دهند:

• یک خانه به جلو بروند.
• از خانه جلویی بپرند (مستقیماً به دو خانه جلوتر بروند.)
• از دو خانه جلویی بپرند (مستقیماً به سه خانه جلوتر بروند.)

برنامه شما باید تعداد همه راه‌های ممکن برای رسیدن باستان‌شناسان به کلید را محاسبه کند.

ورودی

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

خروجی

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

مثال

ورودی نمونه ۱

21
B..T.T....TT.T.T....K

خروجی نمونه ۱

198

ورودی نمونه ۲

5
B..TK

خروجی نمونه ۲

3

ورودی نمونه ۳

30
B..T.....TT..T.T...TTT..T.T..K

خروجی نمونه ۳

0

ورودی نمونه ۴

50
B..T..T.T..TT...T.T..T.TT.T....T.T...TT.T..T....TK

خروجی نمونه ۴

93312