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$ літер. Щоб визначити ймовірність вгадування оригінального повідомлення, знайдіть кількість можливих повідомлень, які могли перетворитися у те, яке Ви отримали.