We should do DP to find the number of ways to form a prefix of the formula so that \(A_i\) follows a + or a -.

More specifically, we should let \(dp[i][j]\) to be the number of ways to arrange a total of \(i\) signs so that no two -s occur in a row and the last sign is + if \(j=0\) and - if \(j=1\).

For each \(2 \leq i \leq N\), if we fix the sign that comes just before \(A_i\), we can independently decide the first \(i-2\) signs and the last \(N-i\) signs, and we can find the number of ways to set them using the values in \(dp\) above.

The complexity of this solution is \(O(N)\).