P17371 [ECNA 2023] Prof. Fumblemore and the Collatz Conjecture

The ***Collatz function***, C(*n*), on positive integers is: $$ C(n)=\begin{cases}n/2,&n\text{ is even},\\3n+1,&n\text{ is odd}.\end{cases} $$ The ***Collatz sequence***, CS(*n*), of a positive integer, *n*, is the sequence $$ 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, ... The ***Collatz Conjecture*** (also known as the *3n+1 problem*) is that CS(*n*) for every positive integer *n* eventually ends repeating the sequence 4, 2, 1. To date, 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 letters E and O (for even and odd) which describe the parity of the values in CS(*n*) up to but not including the first power of 2. So, $$ CST(12)=\texttt{EEOEO}. $$ Note that $$ CS(908)=908,454,227,682,341,1024,512,256,128,64,32,16,8,4,2,1,\ldots $$ so 12 and 908 have the same CST. Prof. Fumblemore needs a program which allows him to enter 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 which 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*) - There can not be two O's in succession (C(odd) = even) - Since, Prof. Fumblemore does not type well, 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 no two O's are adjacent.

Input consists of one line containing a string of up to 50 letters composed of E's and O's.

There is one line of output that consists of the string `INVALID` if the input line is invalid, or a single decimal integer, *n*, such that *n* is the *smallest* integer for which CST(*n*) is the input sequence. Input will be chosen such that $\emph{n} \le 2^{47}$.