Let \(f(S_1,...,S_N)\) be the answer for \(S_1,...,S_N\).

• When \(S_N\) is AND, both \(y_{N-1}\) and \(x_N\) should be \(\text{True}\). Hence, \(f(S_1,...,S_N)=f(S_1,...,S_{N-1})\).
• When \(S_N\) is OR, \(y_{N-1}\) does not matter if \(x_N\) is \(\text{True}\); if \(x_N\) is \(\text{False}\), then \(y_{N-1}\) must be \(\text{True}\). Hence, \(f(S_1,...,S_N)=2^N+f(S_1,...,S_{N-1})\).

Therefore, the problem has been solved in a total of \(O(N)\) time.