\(h(i)\) は C-recursive sequence であり，その特性多項式は \((t-2)^{N+1}(t-1)^{N+1}\) である． よって Bostan-Mori を行えば \(h(X)\) の値が計算できる．

全体計算量 \(O(N \log N \log X)\)

回答例(C++)