SMS
Повідомлення SMS стільникового телефону MOBILA складені з прописних латинських літер. Якщо літера перша на кнопці, потрібно натискувати цю кнопку один раз, щоб додати літеру у повідомлення. Якщо літера друга - потрібно натискувати кнопку двічі і т.д. Так, щоб набрати слово "SMS", потрібно натиснути
(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)
Щоб ввести дві літери, які знаходять на одній кнопці, потрібно між натисканнями клавіша зробити паузу. Наприклад, щоб ввести повідомлення "AA", потрібно натиснути
(ABC)(пауза)(ABC)
Якщо на кнопці три літери, то, як тільки така кнопка натиснута три рази, остання літера додається у повідомлення негайно, а наступні натиснення тієї ж кнопки відносяться до наступної літери повідомлення. Аналогічно, якщо на кнопці чотири літери, то після чотирьох натиснень у повідомлення буде додано останню літеру. Тобто послідовність натиснень
(ABC)(ABC)(ABC)(ABC)(пауза)(ABC)
відопвідає повідомленню "CAA". На жаль, стільникові телефони цієї моделі давно не випускаються, і залишився лише один такий телефон. Він может довільним чином вставляти та ігнорувати паузи підочас введення повідомлення, що може призвести до деяких змін у повідомленнях. Наприклад, увівши MOSCOWQUARTERFINAL, можна отримати замість цього OMSCMNWQTTARTERPDEINAL. Ви отримали SMS-повідомлення і знаєте, що оригінальне повідомлення містило N літер. Щоб визначити ймовірність вгадування оригінального повідомлення, знайдіть кількість можливих повідомлень, які могли перетворитисься у те, яке Ви отримали.
Вхідні дані
У першому рядку задано довжину оригінального повідомлення N. Другий рядок містить отримане SMS-повідомлення.
1 ≤ N ≤ 80, отримане повідомлення складається лише з прописних латинських літер, довжина отрманого повідомлення - від 1 до 80 літер.
Вихідні дані
Вивести кількість повідомлень з N літер, які будучи набрані на цьому телефоні, можуть перетворитись у задане.