Boolean Parenthesization
mediumDynamic Programming II+20 XPTime limit 3s
An expression alternates the values T (true) and F (false) with the operators & (AND), | (OR) and ^ (XOR), for example T|F&T^F. Count the number of ways to fully parenthesise it so that it evaluates to true. Print the count modulo 1 000 000 007.
Input: one line with the expression (no spaces).
Output: the number of ways modulo 10⁹ + 7.
Constraints: the expression has n values and n − 1 operators, 1 ≤ n ≤ 150.
Example: T^F&T has two bracketings: (T^F)&T is true and T^(F&T) is true, so the answer is 2.
Think about it: interval DP counting both outcomes: T[i][j] and F[i][j] = ways for values i … j to become true / false. Split at every operator k between them and combine: for &, true needs both sides true; for |, true unless both are false; for ^, true when the sides differ. O(n³).
Sample input 1
T^F&T
Sample output 1
2
Sample input 2
T|F&T^F
Sample output 2
5
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).