Fito came across a new feature on his mobile phone – T9 input! His phone has a keyboard consisting of numbers looking like this:
In order to input a word using this keyboard, one needs to press a key multiple times for the required letter. More specifically, if the required letter is the first letter mapped to the key, one key press is needed, if it’s the second, two key presses are needed and so on. For instance, if we want to input the word “giht”, we will press the following keys: g-4 i-444 h-44 t-8.
The new possibility Fito discovered
enables you to input text more easily because you don’t need several presses per letter anymore,
just one. The software will try to figure out what word from the dictionary you are trying to input.
Fito is quite sceptical of new technologies (at least new for him) and he is afraid that errors will be
frequent. That is the reason why he decided to test his hypothesis that the errors are frequent. Marko
knows by heart the whole dictionary in the mobile phone. The dictionary consists of
The first line of input contains the integer
The first and only line of output must contain the number of words from the dictionary possible to
construct from the letters on the keys determined by the string