\(k\) についての答えを \(f(k)\) とします。

この時、 \(\displaystyle f(k) = \prod_{i=1}^N \dbinom{A_i + k -1}{A_i}\) です。

このまま求めると時間制限に間に合わないので、前の計算結果を利用することを考えます。

\[\begin {aligned}\displaystyle &\displaystyle f(k+1) = f(k) \times \prod_{i=1}^N \frac{\binom{A_i + k}{A_i}}{\binom{A_i + k -1}{A_i}} \\ \Leftrightarrow &\displaystyle f(k+1) = f(k) \times \prod_{i=1}^N \left (\frac{(A_i + k)!}{A_i! \times k!} \times \frac{A_i! \times (k-1)!}{(A_i + k - 1)!} \right ) \\ \Leftrightarrow &\displaystyle f(k+1) = f(k) \times \prod_{i=1}^N \frac{A_i + k}{k} \\ \Leftrightarrow &\displaystyle f(k+1) = f(k) \times \frac{\prod_{i=1}^N (A_i + k)}{k^N} \\ \Leftrightarrow &\displaystyle f(k+1) = f(k) \times \prod_{i=1}^N (A_i + k) \times k^{-N} \end {aligned}\]

\(k^{-N}\) は繰り返し二乗法によって \(\Theta (\log \mathrm{mod})\) で求まるため、 \(\displaystyle \prod_{i=1}^N (A_i + k)\) の \(k = 1,2, \ldots , M-1\) での値が高速に求まればよいです。

この値は \(\displaystyle g(x) := \prod_{i=1}^N (x + A_i)\) とおいたときの \(g(1), g(2), \ldots , g(M-1)\) の値に一致します。

\(g(x) = c_Nx^N + c_{N-1}x^{N-1} + \ldots + c_0\) を満たす数列 \(c\) は分割統治 + FFT によって \(\Theta(N\log^2N)\) で求まります。

また、多点評価を用いれば \(g(1), g(2), \ldots ,g(M-1)\) の値が \(\Theta(N\log N+M\log^2M)\) で求まります。

よって、 \(g(k) \times k^{-N}\) を \(f(1) = 1\) に順次かけていくことでこの問題を解くことができます。

全体での計算量は \(\Theta (N\log^2N + M\log^2M + M\log \mathrm{mod})\) となります。