公式解説の内容を前提として、時間計算量 \(\mathrm{O}(\log(M) + \log(\mathrm{mod}))\) のアルゴリズムを解説します。 本アルゴリズムは yakisoba_tabetai との議論で発見されました。

\(k\) を \(2^k \leq M\) を満たす最大の整数とします。 このとき、求める答えは\(\displaystyle [x^N] \left( \prod_{i=0}^{k-1} (1+2^i x) \right) (1 + (M - 2^k + 1)x) = [x^N] \left( \prod_{i=0}^{k-1} (1+2^i x) \right) + (M - 2^k + 1)[x^{N-1}]\left( \prod_{i=0}^{k-1} (1+2^i x) \right)\) です。

\(\displaystyle P(x) \coloneqq \prod_{i=0}^{k-1} (1+2^i x)\) と置くと \(P(x) (1+2^kx) = (1+x)P(2x)\) が成り立ちます。 両辺の \([x^{n+1}]\) の係数に着目することで \([x^{n+1}]P(x) + 2^k [x^n]P(x) = 2^{n+1}[x^{n+1}]P(x) + 2^n[x^n]P(x)\) となり、これを変形すると \(\displaystyle [x^{n+1}]P(x) = \frac{2^n - 2^k}{1 - 2^{n+1}} [x^n]P(x)\) を得ます。この漸化式に従い \([x^n]P(x)\) を順に計算することで、\([x^n]P(x)\) を \(\mathrm{O}(n + \log(\mathrm{mod}))\) で計算することができます。

実装例 https://atcoder.jp/contests/arc141/submissions/32097085