\includegraphics{https://static.e-olymp.com/content/53/53fc1c47f7cf21fd36bde0e357de94560b540aa1.jpg} \textbf{SMS} messages cell phone \textbf{MOBILA} composed of capital letters. If the first letter on the button, you press this button once to add a letter in the message. If the letter is the second - you need to press the button twice, etc. So, to type the word "\textbf{SMS}", you need to press \textbf{(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)} To enter two letters are on one button, you from pressing pause. For example, to enter a message "\textbf{AA}", you need to press \textbf{(ABC)(pause)(ABC)} If the button three letters, then as soon as this button is pressed three times, the last letter added to the message immediately, and the next pressing the same button again refer to the next letter of the message. Similarly, if a button on the four letters, then after four clicks in the message will be added to the last letter. That is the sequence of keystrokes \textbf{(ABC)(ABC)(ABC)(ABC)(pause)(ABC)} message "\textbf{CAA}". Unfortunately, the cell phones of this model have not produced, and there was only one such phone. It can randomly insert and ignore pauses while typing messages, which may lead to some changes in messages. For example, typing \textbf{MOSCOWQUARTERFINAL}, you can get instead \textbf{OMSCMNWQTTARTERPDEINAL}. You have received an SMS-message and know that the original message contains \textbf{N} letters. To determine the probability of guessing the original message, find the number of possible messages that may have become that which you received. \InputFile The first line specifies the length of the original message \textbf{N}. The second line contains the received \textbf{SMS}-message. \textbf{1} ≤ \textbf{N} ≤ \textbf{80}, the received message contains only uppercase letters, the length of the message received - from \textbf{1} to \textbf{80} letters. \OutputFile Deduce the number of messages of \textbf{N} letters, which, when dialed on this phone can turn into this.