AtCoder Regular Contest 212 - ARC212 C - ABS Ball の解法です． shobonvip さんによるユーザ解説 そのままみたいなものですが， 式の導出のところを多めに書きました．
問題概要
$N$ 個の区別できない白いボールと，$M$ 個の区別できる箱がある． 「各ボールを赤・青どちらかの色に塗っていずれかの箱に入れる」方法それぞれに対して， $i$ 番目の箱に入った赤，青のボールの数を $a_i$, $b_i$ として $\prod_{1 \leq i \leq M} | a_i - b_i |$ を計算した場合の総和を mod 998244353 で求めよ．
制約:
$1 \leq N \leq 10^7$， $1 \leq M \leq 10^7$
解
$a + b = n$ である非負整数 $(a, b)$ についての $|b - a|$ の和を $c_n$ と書くことにすると， 冪級数 $f = \sum_n c_n x^n$ を使って，求める答が $[x^N] f^M$ と表せることに注意する．
$2p + q = n$ となる非負整数 $(p, q)$ の組は，$a + b = n$ である非負整数 $(a, b)$ の組と， $p = \min(a, b), q = |a - b|$ という関係のもと，だいたい 1 : 2 に対応する． $q = 0$ のときには対応する $(a, b)$ は1組しかないが，このときには $|a - b| = 0$ である． したがって，$c_n$ は，$2p + q = n$ である非負整数 $(p, q)$ についての $q$ の和の 2 倍に等しい． つまり，$c_n = [x^n] (2\sum_p x^{2p}\sum_q qx^q)$ である． 括弧の中に $n$ が現れていないことに注意して，$f = 2\sum_p x^{2p} \sum_q qx^q$ を得る．
あとは計算になる．負の二項定理 $\frac{1}{(1 - x)^d} = \sum_n \binom{n + d - 1}{d - 1} x^n$ を使う．
$\sum_p x^{2p} = \frac{1}{1 - x^2}$
$\sum_q qx^{q} = x\sum_q (q + 1)x^{q} = x\sum_q \binom{q + 2 - 1}{2 - 1}x^q = \frac{x}{(1 - x)^2}$
したがって，求める答は，
$[x^N]f^M = [x^N]\frac{2^M x^M}{(1 - x^2)^M (1 - x)^{2M}} = 2^M [x^{N - M}] \frac{1}{(1 - x^2)^M (1 - x)^{2M}} $
である．$\frac{1}{(1 - x^2)^M}$ も $\frac{1}{(1 - x)^{2M}}$ も負の二項定理で展開できるので， これらの積の $x^{N - M}$ の係数を具体的に求めることができる．