Задачі
SMS
SMS
\includegraphics{https://static.e-olymp.com/content/53/53fc1c47f7cf21fd36bde0e357de94560b540aa1.jpg}
Повідомлення \textbf{SMS} стільникового телефону \textbf{MOBILA} складені з прописних латинських літер. Якщо літера перша на кнопці, потрібно натискувати цю кнопку один раз, щоб додати літеру у повідомлення. Якщо літера друга - потрібно натискувати кнопку двічі і т.д. Так, щоб набрати слово "\textbf{SMS}", потрібно натиснути
\textbf{(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)}
Щоб ввести дві літери, які знаходять на одній кнопці, потрібно між натисканнями клавіша зробити паузу. Наприклад, щоб ввести повідомлення "\textbf{AA}", потрібно натиснути
\textbf{(ABC)(пауза)(ABC)}
Якщо на кнопці три літери, то, як тільки така кнопка натиснута три рази, остання літера додається у повідомлення негайно, а наступні натиснення тієї ж кнопки відносяться до наступної літери повідомлення. Аналогічно, якщо на кнопці чотири літери, то після чотирьох натиснень у повідомлення буде додано останню літеру. Тобто послідовність натиснень
\textbf{(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)}
відопвідає повідомленню "\textbf{CAA}". На жаль, стільникові телефони цієї моделі давно не випускаються, і залишився лише один такий телефон. Він может довільним чином вставляти та ігнорувати паузи підочас введення повідомлення, що може призвести до деяких змін у повідомленнях. Наприклад, увівши \textbf{MOSCOWQUARTERFINAL}, можна отримати замість цього \textbf{OMSCMNWQTTARTERPDEINAL}. Ви отримали \textbf{SMS}-повідомлення і знаєте, що оригінальне повідомлення містило \textbf{N} літер. Щоб визначити ймовірність вгадування оригінального повідомлення, знайдіть кількість можливих повідомлень, які могли перетворитисься у те, яке Ви отримали.
\InputFile
У першому рядку задано довжину оригінального повідомлення \textbf{N}. Другий рядок містить отримане \textbf{SMS}-повідомлення.
\textbf{1} ≤ \textbf{N} ≤ \textbf{80}, отримане повідомлення складається лише з прописних латинських літер, довжина отрманого повідомлення - від \textbf{1} до \textbf{80} літер.
\OutputFile
Вивести кількість повідомлень з \textbf{N} літер, які будучи набрані на цьому телефоні, можуть перетворитись у задане.
Вхідні дані #1
4 MAMA
Вихідні дані #1
1