对于正整数 $n$，Collatz 函数 $C(n)$ 定义为： 若 $n$ 为偶数，则 $C(n) = n/2$；若 $n$ 为奇数，则 $C(n) = 3n+1$。

正整数 $n$ 的 Collatz 序列 $CS(n)$ 为序列： $$CS(n) = n, C(n), C(C(n)), C(C(C(n))), \dots$$

例如，$CS(12) = 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, \dots$

Collatz 猜想（也称为 $3n+1$ 问题）认为，对于每个正整数 $n$，$CS(n)$ 最终都会进入 $4, 2, 1$ 的循环。迄今为止，该猜想的状态仍然未知。目前尚未给出证明，在很大的数值范围内也没有找到反例。

Fumblemore 教授希望利用 Collatz 序列类型来研究这个问题。整数 $n$ 的 Collatz 序列类型 (CST) 是一个由字母 E 和 O（分别代表偶数和奇数）组成的序列，它描述了 $CS(n)$ 中直到第一个 2 的幂（不包含该 2 的幂）之前所有项的奇偶性。因此： $$\text{CST}(12) = \text{EEOEO}$$

注意： $$CS(908) = 908, 454, 227, 682, 341, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 3, 2, \dots$$ 所以 12 和 908 具有相同的 CST。

Fumblemore 教授需要一个程序，输入一个由 E 和 O 组成的序列，并返回满足 $\text{CST}(n)$ 等于该序列的最小整数 $n$。

说明： E 代表不是 2 的幂的偶数。 O 代表大于 1 的奇数。 序列的最后一个字母必须是 O（如果 $C(n)$ 是 2 的幂，则 $n$ 也是）。 序列中不能有两个连续的 O（因为 $C(\text{奇数}) = \text{偶数}$）。 * 由于 Fumblemore 教授打字不太规范，在尝试寻找 $n$ 之前，你必须检查输入序列是否有效。即：序列仅包含 E 和 O，以 O 结尾，且没有两个 O 相邻。

输入格式

输入包含一行，为一个长度不超过 50 的字符串，由 E 和 O 组成。

输出格式

输出一行，如果输入序列无效，则输出字符串 INVALID；否则输出一个十进制整数 $n$，使得 $n$ 是满足 $\text{CST}(n)$ 等于输入序列的最小整数。输入保证满足 $n \le 2^{47}$。

样例

样例输入 1

EEOEO

样例输出 1

12

样例输入 2

EEOOEO

样例输出 2

INVALID