For convenience, let \(B_0=B_N=0\). Let \(a_i\) be the total amount by which \(A_i\) decreases, and \(b_i\) be the total amount by which \(B_i\) decreases. For a fixed pair of \(a\) and \(b\), let us consider whether it is achievable. It turns out that it is achievable if and only if all of the following hold:

• \(0 \leq a_i \leq A_i\)
• \(0 \leq b_i \leq B_i\)
• \(a_i+b_{i-1}+b_i\) is even. (Treat \(b_0\) and \(b_{N}\) as \(0\).)
• No number accounts for more than half of \(a_i,b_{i-1},b_i\).

From this, if \(B_{i-1}+A_i<B_i\), we have no problem replacing \(B_i\) with \(B_{i-1}+A_i\). We can also do similarly for the case \(B_i+A_i<B_{i-1}\). By repeating this operation, we can ensure \(|B_{i-1}-B_i| \leq A_i\) for each \(i\).

Next, if there is \(i\) such that \(A_i \geq B_{i-1}+B_i\), we can divide the problem into \([1,i]\) and \([i,N]\). This is because \(a_i=b_{i-1}+b_i\) should hold for any case, and the solution for \([1,i]\) and that for \([i,N]\) do not interfere with each other.

Thus, if we divide the whole interval with such indices \(i\) and count the optimal solutions for each interval after division, the product of those counts will be the final answer.

Now, let us assume \(A_i < B_{i-1}+B_i\) holds for each \(2 \leq i \leq N-1\). We will consider whether it is possible to achieve \(a_i=A_i\) for all \(i\). First, if \(S=\sum A_i\) is even, it turns out it is possible. Specifically, we can achieve it by choosing \(b_i=B_i\) or \(b_i=B_i-1\) for each \(i\) carefully to match the parities. If \(S\) is even, the maximum value of \(\sum a_i\) that can be achieved is \(S-1\). Specifically, we can achieve \(a_1=A_1-1\) and \(a_i=A_i\) for all \(2 \leq i\) in a way similar to the above. This enables us to see that we only need to consider solutions where only one of \(a_i\) is \(A_i-1\). Now, we just have to actually determine, for each \(i\), whether the solution with \(a_i=A_i-1\) is achievable. For each \(i=1,2,\cdots,k\), the values that \(b_k\) can take when \(a_i=A_i\) can be represented with a parity and an interval. We will thus find such intervals in ascending order of \(k\) with DP. Let us also do this backward. Then, combining these pieces of information, we can see whether the solution with \(a_i=A_i-1\) is achievable for each \(i\).

The total complexity of our approach is \(O(N)\).