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

定义正整数上的 Collatz 函数 $C(n)$： $$ C(n)= \begin{cases} \dfrac n2,&n\text{ 为偶数},\\ 3n+1,&n\text{ 为奇数}. \end{cases} $$ 正整数 $n$ 的 Collatz 序列 $CS(n)$ 为 $$ CS(n)=n,C(n),C(C(n)),C(C(C(n))),\ldots $$ 例如， $$ CS(12)=12,6,3,10,5,16,8,4,2,1,4,2,1,\ldots $$ Collatz 猜想也称 $3n+1$ 问题，它断言每个正整数 $n$ 的 $CS(n)$ 最终都会进入重复序列 $4,2,1$。时至今日，这一猜想仍未解决：既没有证明，也没有在非常大的范围内找到反例。 Fumblemore 教授想用“Collatz 序列类型”研究这个问题。整数 $n$ 的 Collatz 序列类型记作 $CST(n)$，它是由字母 `E` 和 `O` 组成的序列，分别表示 $CS(n)$ 中各项的奇偶性，记录到第一个 $2$ 的幂出现之前，但不包含这个 $2$ 的幂。因此 $$ CST(12)=\texttt{EEOEO}. $$ 又因为 $CS(908)$ 在到达第一个 $2$ 的幂前依次为 $$ 908,454,227,682,341, $$ 下一项为 $1024$，所以 $12$ 和 $908$ 具有相同的 $CST$。 Fumblemore 教授需要一个程序：输入一串 `E` 和 `O`，返回满足该字符串等于 $CST(n)$ 的最小整数 $n$。 注意： - `E` 对应不是 $2$ 的幂的偶数； - `O` 对应大于 $1$ 的奇数； - 序列最后一个字符必须是 `O`，因为若 $C(n)$ 是 $2$ 的幂，则 $n$ 也是 $2$ 的幂； - 不能有两个连续的 `O`，因为奇数经过 $C$ 后会变成偶数； - Fumblemore 教授不擅长打字，因此在求 $n$ 前必须检查输入是否合法：字符串只能包含 `E` 和 `O`，必须以 `O` 结尾，并且不能有相邻的两个 `O`。

输入一行，包含一个长度不超过 $50$ 的字符串。

如果输入字符串不合法，输出 `INVALID`；否则输出一个十进制整数 $n$，表示满足 $CST(n)$ 等于输入字符串的最小整数。保证测试数据中的答案满足 $n\le 2^{47}$。