\(N\) 頂点の木であって、頂点 \(i\) の次数が \(d_i\) であるようなものの個数は \(\sum d = 2N-2\) という条件下で以下のようになります。

\[ \frac{(N-2)!}{\prod_{i=1}^{N} (d_i-1)!} \]

さて、問題文の条件は以下のように言い換えられます。

• 頂点 \(1\) の次数は素数次
• 頂点\(i(2 \le i \le N)\) の次数は素数 + 1 次もしくは 1 次

よって、

\[f(x) = \sum_{p : prime} \frac{x^p}{(p-1)!},g(x) = x + \sum_{p:prime} \frac{x^{p+1}}{p!}\]

と定義したときの \((N-2)! [x^{2N-2}] f(x)g(x)^{N-1}\) が答えとなります。FPS pow を用いることで \(\mathrm{O}(N \log N)\) で計算できます。