\(\displaystyle S=\sum_{i=1}^{N}A_i\) としたときに，

\[\left[x^{S+y}\right]\prod_{i=1}^{N}\left(1+x^{A_i}+x^{2A_i}\right)\neq0\]

なる \(0\leq y\leq S\) の個数を求めればよい．これを分割統治 NTT することで答えを求めたいが，例えば法を \(998244353\) と取ったとき，NTT の過程で「非ゼロの係数を \(1\) に置換する」という処理を行えば，\(2S+1< 998244353\) なので \(\bmod 998244353\) 上で計算しても，上の条件は正しく判定されることがわかる．
　なお，非ゼロの係数を適切に置換する処理を行わないと WA になる可能性があるが，そのようなテストケースは入っていないようである．