便利のため，\(B_0=B_N=0\) とします． \(A_i\) が減る総量を \(a_i\)，\(B_i\) が減る総量を \(b_i\) で表し，\(a,b\) を決めてそれが達成可能かを考えることにします． これは，以下の条件がすべて成り立つことが必要十分です．

• \(0 \leq a_i \leq A_i\)
• \(0 \leq b_i \leq B_i\)
• \(a_i+b_{i-1}+b_i\) が偶数．（\(b_0,b_{N}\) は \(0\) として扱う）
• \(a_i,b_{i-1},b_i\) の中で，過半数になるような数が存在しない．

これより，もし \(B_{i-1}+A_i<B_i\) であれば，\(B_i\) を \(B_{i-1}+A_i\) で置き換えても問題ありません． \(B_i+A_i<B_{i-1}\) の場合も同様にできます． この操作を繰り返し行えば，\(|B_{i-1}-B_i| \leq A_i\) がすべての \(i\) について成立するようになります．

次に，\(A_i \geq B_{i-1}+B_i\) なる \(i\) があれば，問題を \([1,i]\) と \([i,N]\) に分割して考えることができます． これは，どのような場合でも \(a_i=b_{i-1}+b_i\) となるのが最適であり，\([1,i]\) の解と \([i,N]\) の解が互いに干渉しないためです．

よって，このような \(i\) で区間を分割し，各区間で最適解を達成する方法が何通りあるかを求めれば，その積が最終的な答えになります．

今，\(2 \leq i \leq N-1\) について，\(A_i < B_{i-1}+B_i\) が成り立つとします． すべての \(i\) で \(a_i=A_i\) を達成することが可能かどうかを考えます． まず，\(S=\sum A_i\) が偶数ならば，これは可能です． 具体的には，各 \(i\) について \(b_i=B_i\) もしくは \(b_i=B_i-1\) として，うまく偶奇を合わせていくと，達成できることがわかります． \(S\) が奇数の場合は，\(\sum a_i\) の最大値は \(S-1\) になります． 具体的には，\(a_1=A_1-1,a_i=A_i\) for all \(2 \leq i\) が上と同様に達成できます． つまり，\(a_i\) の中でどれかひとつだけが \(A_i-1\) になっているような解だけを考えれば良いとわかります． ここまで分かれば，各 \(i\) について実際に \(a_i=A_i-1\) となる解が達成可能かを判定すれば良いです． 各 \(i=1,2,\cdots,k\) について \(a_i=A_i\) としたときに \(b_k\) としてあり得る値は，偶奇と区間で表すことが可能です． よってこの区間を \(k\) の昇順に DP で求めます． これを後ろからも求めておきます． あとは，これらの情報を合わせれば，各 \(i\) について \(a_i=A_i-1\) となる解が達成可能かどうかわかります．

計算量は全体で \(O(N)\) です．