自己辺が無く、各頂点の次数が \(2\) 以下であるという条件から、各連結成分はパス（孤立点を含む）かサイクルのどちらかになります。

連結成分のサイズの最大値が \(L\) である場合の数は、最大値が \(L\) 以下である場合の数 - 最大値が \(L-1\) 以下である場合の数で求まります。以降、連結成分のサイズの最大値が \(S\) 以下である場合の数を求める問題を考えます。

動的計画法を用います。番号の小さい頂点から順に属する連結成分について決めていきます。\(DP[vcnt][ecnt]:=\) これまでに属する連結成分を定めた頂点が \(vcnt\) 個、使った辺が \(ecnt\) 個であるときの、属する連結成分を定めた頂点の誘導部分グラフの総数とします。まだ連結成分が定まっていない頂点の中で最も番号の小さい頂点を \(x\) とおき、\(x\)の属する連結成分を決めることによる遷移を考えます。

• \(1 \leq S\) で、 \(x\) が孤立点のとき

\(x\) の成分は \(1\) 通り。

\(DP[vcnt+1][ecnt]+=DP[vcnt][ecnt]\) と遷移する。

• \(x\) が頂点数 \(k(2 \leq k \leq S)\) のパスに属するとき

\(x\) の成分は、属する頂点が \(C(N-vcnt-1,k-1)\) 通り、辺が \(k!/2\) 通り。

\(DP[vcnt+k][ecnt+k-1]+=DP[vcnt][ecnt] \times C(N-vcnt-1,k-1) \times k!/2\) と遷移する。

• \(2 \leq S\) で、 \(x\) が頂点数 \(2\) のサイクルに属するとき

\(x\) の成分は、属する頂点が \(N-vcnt-1\) 通り、辺が \(1\) 通り。

\(DP[vcnt+2][ecnt+2]+=DP[vcnt][ecnt] \times (N-vcnt-1)\) と遷移する。

• \(x\) が頂点数 \(k(3 \leq k \leq S)\) のサイクルに属するとき

\(x\) の成分は、属する頂点が \(C(N-vcnt-1,k-1)\) 通り、辺が \((k-1)!/2\) 通り。

\(DP[vcnt+k][ecnt+k]+=DP[vcnt][ecnt] \times C(N-vcnt-1,k-1) \times (k-1)!/2\) と遷移する。

ただし、\(C(n,k)\) は二項係数を表し、逆元テーブルを用いた方法や動的計画法なので事前に求めておきます。計算量は \(O(NML)\) です。