包除原理を発動すると

\[f(x) = \sum_{i\equiv 0\pmod{3}}\frac{x^i}{i!}-\sum_{i\equiv 1\pmod{3}}\frac{x^i}{i!} \]

としたとき \(ANS=N![x^N]\frac{1}{f(x)}\) ということになる．なお OEIS にもある．

本問題の mod で \(1\) の原始 \(3\) 乗根がとれることに注意して，root of unity filter を発動すると \(f(x)=ae^{bx}+ce^{dx}\) の形になっている．

\[ANS=N![x^N]\frac{ae^{bx}}{1-ce^{dx}}\]

の形になる（形，と言っているだけで \(a,b,c,d\) は上の式を引き継ぎません，以下同様）．

\(u=e^{dx}-1\) とおく．\(ANS=N![x^N]\frac{ae^{bx}}{1-cu}\) の形．\(u\) は定数項が \(0\) であることに注意すると

\[ANS=N![x^N]ae^{bx}\cdot \frac{1-(cu)^{N+1}}{1-cu}\]

の形．\(t = e^{dx}\) とすると

\[ANS=N![x^N]ae^{bx}\cdot \frac{1-(c(t-1))^{N+1}}{1-c(t-1)}\]

の形．ここは \(u, t\) の関係 \(u=t-1\) の関係を使って \(f(u)\) を \(f(t-1)\) に書き換えるという操作をしているが，「\(u\) の FPS の \(N\) 次以下」ではなく「\(u\) の \(N\) 次多項式」だから上手くいっている．

\(\frac{1-(c(t-1))^{N+1}}{1-c(t-1)}\) は普通に \(t\) の多項式で，係数は \(O(N)\) 時間で求まる．結局

\[ANS=N![x^N]ae^{bx}\sum_{0\leq i\leq N}c_ie^{dix}\]

の形になる．これは \(a\sum_i c_i (b+di)^N\) である．