形式的冪級数の pow で通せた！

問題概要

$N$ 個の箱それぞれに正しい括弧列を入れる。ただし、次の2つの条件をともに満たすように入れる必要がある。

条件を満たす入れ方の総数を 998244353 で割ったあまりを求めよ。

制約

長さが $2k$ となる「正しいカッコ列」の個数はカタラン数と呼ばれるもの ( $c(k)$ と書くことにする)。

$c(k) = \frac{{}_{2n}{\rm C}_{n}}{n+1}$

が成り立つ。

そして、今回の問題は形式的冪級数の知見を活用すると、

$f(x) = c(0) + c(1)x^{1} + c(2)x^{2} + \dots + c(M)x^{M}$ 　(ただし $c(K)x^{K}$ の項のみ除く)

として、 $\lbrack x^{M} \rbrack f(x)^{N}$ を求めれば OK だとわかる。そしてこれは $O(M \log M)$ で求められる。yosupo juege から速い FPS のコードを借用することで通った！！

しかし実際には、 $O(N + M)$ で求められる解法があったらしくて、すごい！！！