题目描述

定义正整数上的 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}$。

EEOEO

12

EEOOEO

INVALID