Prof. Fumblemore and the Collatz Conjecture

The Collatz function $C(n)$ on positive integers is:

• $C(n) = n/2$ if $n$ is even
• $C(n) = 3n+1$ if $n$ is odd

The Collatz sequence $CS(n)$ of a positive integer $n$ is $CS(n) = n, C(n), C(C(n)), C(C(C(n))), \ldots$

For example, $CS(12) = 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \ldots$

The Collatz Conjecture (also known as the 3n+1 problem) states that $CS(n)$ for every positive integer $n$ eventually ends by repeating 4, 2, 1. The status of this conjecture is still unknown. No proof has been given, and no counterexample has been found up to very large values.

Prof. Fumblemore wants to study the problem using Collatz sequence types. The Collatz sequence type (CST) of an integer $n$, $CST(n)$, is a sequence of the letters E and O (for even and odd) that describe the parity of the values in $CS(n)$ up to but not including the first power of 2. So,

$CST(12) = EEOEO$

Note that

$CS(908) = 908, 454, 227, 682, 341, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 3, 2, \ldots$

so 12 and 908 have the same CST.

Prof. Fumblemore needs a program that takes a sequence of E's and O's and returns the smallest integer $n$ for which the given sequence is $CST(n)$.

Notes:

• E's are even numbers that are not powers of 2.
• O's are odd numbers greater than 1.
• The last letter in a sequence must be an O (if $C(n)$ is a power of 2, so is $n$).
• Two O's cannot be adjacent, since $C(\text{odd})$ is even.
• Prof. Fumblemore does not type well, so you must check that the input sequence is valid before attempting to find $n$. That is, the sequence contains only E's and O's, ends in O, and has no two O's adjacent.

One line containing a string of up to 50 letters, each either E or O.

One line containing INVALID if the input sequence is invalid. Otherwise, one line containing the smallest integer $n$ such that $CST(n)$ is the input sequence. The input is chosen so that $n \le 247$.