SMS

SMS messages of the cell phone MOBILA are composed of capital letters. If the letter is first 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 "SMS", you need to press

(PQRS)(PQRS)(PQRS)(PQRS)(MNO)(PQRS)(PQRS)(PQRS)(PQRS)

To enter two letters that are on one button, you press and release the button with a pause. For example, to enter a message "AA", you need to press

(ABC)(pause)(ABC)

If the button has three letters, then as soon as this button is pressed three times, the last letter is added to the message immediately, and the next presses of the same button refer to the next letter of the message. Similarly, if a button has four letters, then after four clicks the last letter will be added to the message. That is, the sequence of keystrokes

(ABC)(ABC)(ABC)(ABC)(pause)(ABC)

message corresponds to "CAA". Unfortunately, the cell phones of this model have not been produced for a long time, 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 MOSCOWQUARTERFINAL, you can get instead OMSCMNWQTTARTERPDEINAL. You have received an SMS-message and know that the original message contains $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.