まず，\(B_i \ge M\) \((i = 1, 2, \dots, N)\) が成り立っている場合について考えます．このとき，求めたい値は \(A_1, A_2, \dots, A_N\) の \(M\) 次単項式の総和

\[\sum_{m_1 + m_2 + \dots + m_N = M,~m_i \ge 0} A_1^{m_1} A_2^{m_2} \cdots A_N^{m_N}\]

で表されます．この式をグッと睨んで変形すると，

\[\sum_{i=1}^N \frac{A_i^{M+N-1}}{\prod_{j \neq i} (A_i - A_j)}\]

が得られます．（正当性は \(N\) に関する数学的帰納法で証明できます．\(N = 2\) の場合を等比数列の和の公式を用いて変形してみると分かると思います．） この式に従って計算すれば，求めたい値は \(\mathrm{O}(N \log M + N^2 \log \mathrm{mod})\) 時間で計算できます．

冒頭の仮定を満たさない場合を考えます．この場合は，まず仮定を満たす場合の値を計算し，数え過ぎている分（実際にはカード \(i\) の枚数が足りないような組合せの寄与）を引けばよいです．具体的には，\(\sum_{i \in X} (B_i + 1) \le M\) となるような各部分集合 \(X \subseteq \{1, 2, \dots, N\}\) に関して，「カード \(i \in X\) を \(B_i + 1\) 枚以上使うような場合の寄与」を計算し，包除原理を適用します．「」の値は，冒頭の仮定を満たす場合の \(M\) を \(M - \sum_{i \in X} (B_i + 1)\) で置き換えて得られる値に \(\prod_{i \in X} A_i^{B_i + 1}\) を掛ければ得られます．（カード \(i \in X\) を \(B_i + 1\) 枚使うことを先に決め打っただけと見なせるため．）

\((A_i - A_j)^{-1}\) の値とそれらの積は前計算しておくことで使い回せるので，全体の計算量は \(\mathrm{O}(2^N N \log M + N^2 \log \mathrm{mod})\) となり，これは十分高速です．

実装例 (C, 224 ms)