問題の答えを \(a_N\) とします。また、\(f(x) = \sum_{i=1}^{\infty} \frac{a_ix^i}{i!}\) とします。つまり \(f(x)\) は (根、根付き木) のペアの個数の指数型母関数です。

ここで、頂点 \(1\) が根かつ頂点 \(1\) の子が \(k\) 個である木の個数を数え上げます。そのような木の個数は \((N-1)! [x^{N-1}] \frac{f(x)^k}{k!}\) となります。よって、根の次数が \(k\) 個であるような (根、根付き木) のペアの個数の指数型母関数は \(x\frac{f(x)^k}{k!}\) です。(指数型母関数の \(\frac{1}{(N-1)!}\) が\( \frac{1}{N!}\) になっている \(\frac{1}{N}\) のずれと、根を自由に選べるようになったことによる \(N\) のずれが打ち消しあっています。)

よって、\(k\) を動かすと

\[f(x) = x\left(\sum_{k = 0 \lor k : prime} \frac{f(x)^k}{k!}\right)\]

を得ることが出来ます。つまり、\(g(x) = 1 + \sum_{p : prime} \frac{x^p}{p!}\) として、\(f(x) = xg(f(x))\) です。

ここで、ラグランジュ反転を用います。ラグランジュ反転とは、以下のような定理。です。

形式的冪級数 $F(x),G(x)$ は逆関数の関係にあるとする。(すなわち $F(G(x)) = G(F(x)) = x$ が成り立つ。) 今、$[x^0] F(x) = [x^0] G(x) = 0$ かつ $[x^1] F(x) \neq 0,[x^1] G(x) \neq 0$ が成り立つとき、

$$ [x^n] G(x) = \frac{1}{n} [x^{n-1}] \left(\frac{x}{F(x)}\right)^n $$

が成り立つ。

証明は https://atcoder.jp/contests/abc222/editorial/2742 などをお読みください。

今回の場合、\(\frac{f(x)}{g(f(x))} = x\) であるため、\(h(x) = \frac{x}{g(x)}\) とすると \(f(x),h(x)\) がラグランジュ反転の条件を満たす関係となります。よって、

\[ [x^N] f(x) = \frac{1}{N} [x^{N-1}] \left(\frac{x}{h(x)}\right)^N \]

が成り立ちます。ここで、\(\left(\frac{x}{h(x)}\right) = g(x)\) なので、\([x^N] f(x) = \frac{1}{N} [x^{N-1}] g(x)^N\) となり、FPS pow を計算すれば \(\mathrm{O}(N \log N)\) で計算できます。