形式的べき級数により考察します。指数型母関数を考えることにより、答えは次のように表せます。

\[ D! [x^D] \prod_{k=1}^N \left( \sum_{i \ge a_k} \frac{x^i}{i!} \right) \]

\(e^x = \sum_{i \ge 0} x^i/i!\) を用いて、次のように書き換えます。

\[ D! [x^D] \prod_{k=1}^N \left( e^x - \sum_{i=0}^{a_k-1} \frac{x^i}{i!} \right) \]

この総乗を展開すると、各項は実数 \(c\) と非負整数 \(a,b\) により \(c \times e^{ax} \times x^b\) という形で表されます。

総乗の展開における \(e^{ax} \times x^b\) の係数を \(c_{a,b}\) とします。このとき、答えは

\[ \begin{aligned} D! [x^D] \sum_{a,b} c_{a,b} e^{ax} x^b &= D! \sum_{a,b} c_{a,b} [x^{D-b}] e^{ax}\\ &= D! \sum_{a,b} c_{a,b} \frac{a^{D-b}}{(D-b)!} \\ &= \sum_{a,b} c_{a,b} \frac{D!}{(D-b)!} a^{D-b} \end{aligned} \]

となります。ただし、 \(D-b \ge 0\) の項のみについて総和を取るとします。また、 \(0^0 = 1\) とします。

\(c_{a,b}\) の値は動的計画法を用いて \(O(N^3 (\max A)^2)\) で計算できます。たとえば \(\mathrm{dp}[k][a][b]\) を \(a_k\) まで展開したときの \(e^{ax} x^b\) の係数とすればよいです。ここで、 \(0 \le a \le N, 0 \le b \le N (\max A)\) です。

また、 \(D!\) と \((D-b)!\) は \(D\) が最大 \(10^9\) と大きいため計算することは難しいですが（埋め込みや階乗を高速に計算するテクニックによって可能）、必要な値は \(D!/(D-b)! = D\times (D-1)\times \cdots \times (D-b+1)\) のみであり、掛ける項数が少ないことに注目すると高速に計算できます。

母関数を使わない方法で包除原理を適用するものがありますが、この解法とほとんど同じになると思います。