\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}. Вторая строка содержит полученное SMS-сообщение. \textbf{1} ≤ \textbf{N} ≤ \textbf{80}, полученное сообщение состоит только из прописных латинских букв, длина полученного сообщения - от \textbf{1} до \textbf{80} букв. \OutputFile Вывести число сообщений из \textbf{N} букв, которые, будучи набранными на этом телефоне, могут превратиться в данное.