writer 解説：https://atcoder.jp/contests/arc124/editorial/2332 と大体同じです。DP による計算パートについて、少し異なる見方を説明します。

\(i\) 番目の人が渡す個数を \(x_i\) と書きます。\(x = (x_i)\) の結果の数列の総積を \(f(x)\) と書きます。本問は、結局以下の計算に帰着されます。

• \(f(x) = \prod (a_i - x_i + x_{i-1})\) とする。
• \(\sum_{0\leq x_i \leq a_i} f(x) - \sum_{1\leq x_i \leq a_i} f(x)\) を求めよ。

多項式の区間和を求める問題に帰着されました。区間和は、各 \(i\) について次を行うことで計算できます。

• \(x_i\) について \(k\) 次の項の \(x_i^k\) を \(\sum_{x_i}x_i^k\) に置き換える

\(f(x) = \prod (a_i - x_i + x_{i-1})\) を展開して、すべての項の係数を求めようとすると指数個の係数を管理することになってしまいますが、展開しながら \(x_i\) についての次数が確定した段階で、\(\sum x_i^k\) への置き換えを行うことで、計算の各時点で保持すべき係数は \(4\) つで済み、全体として \(O(N)\) 時間で解くことができます。