4. Neanderthal Numbers

What is the Problem?

Lefty the Neanderthal is in the process of discovering counting for the first time in history. Using the fingers of his right hand, Lefty assigns each of them a name. He names the first finger “ook”, the second finger “ook ook”, the third “oog”, the fourth “ooga” and the fifth “ug”. For many days this is enough, allowing Lefty to quickly express a count to his colleagues in words that are more precise than “many” and “lots”.

One day Lefty was stuck… after he counted ug shiny beads he realized he had more! So he took a look at his right foot and starting naming his toes! He called his toes “mook”, “mook mook”, “oogam”, “oogum” and “ug ug”. Now Lefty can count all kinds of things!

DATA41.txt (DATA42.txt for the second try) will contain 10 test cases. Each test case consists of a single line of text with N (1 ≤ N ≤ 50) Neanderthal number words. The words are not separated by spaces. You must parse each line and print out (on a single line) the number of possible sequences of Neanderthal numbers that can be represented by a Neanderthal person speaking the words aloud (for example the string “ogamookogumook” could be “ooga mook oogum ook” meaning “4 6 9 1” or “oogam ook oogum ook” meaning “8 1 9 1”. Note that the sample input below only contains 2 test cases, but the real data files will contain 10.

Sample Input

ookookook

oogamookoogumook

Sample Output

3

2

Solution

Here is the solution by Logan Cantin.