Problem D
Prof. Fumblemore and the Collatz Conjecture

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

The Collatz sequence, CS(n), of a positive integer, n, is the sequence

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,

Note that

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

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

Output

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 $n \le 2^{47}$.

EEOEO

12

EEOOEO

INVALID