You are given a Boolean expression E = v1p1v2p2, . . . , pn1vn, where for 1 i n, vi is either T or F (corresponding to the Boolean values TRUE and FALSE), and for 1 i n 1, pi is either or the Boolean operators AND and OR. By properly parenthesizing the expression, we may ensure that it evaluates to T or to F. For example, consider the expression F T T. We can parenthesize it as F (T T), and then it evaluates to F. We can also parenthesize it as (F T ) T , and then it evaluates to T . Design an efficient algorithm that computes the number of ways to parenthesize the input expression, so that it will evaluate to T . Prove the algorithms correctness and analyze its running time. Note: we think of parenthesizing as determining the order of operations, so adding extra parentheses that do not affect the order of operations does not count.