A logic relay is described by a string that strictly alternates boolean operands and binary operators, starting and ending with an operand. Each operand is T (true) or F (false); each operator is & (AND), | (OR), or ^ (XOR). There is no whitespace. For example, a valid string looks like T|F&T.
By choosing where to place parentheses, the expression can be evaluated in different orders (the operators are not given any precedence — every grouping is decided purely by your parenthesization). Count the number of distinct full parenthesizations that make the whole expression evaluate to true. Because the count can be large, output it modulo 1000000007.
Two parenthesizations are considered the same only if they group operands identically.
Input format
A single line containing the expression string (operands T/F separated by operators &, |, ^).
Output format
A single integer: the number of parenthesizations evaluating to true, modulo 1000000007.
Constraints
- The string length is odd and between 1 and 199.
- The number of operands is between 1 and 100.