\(N=1\) のときは明らかです。以降 \(3 \leq N\) とします。

一旦 \(4\) 番目の条件はないものとして考えます。

[1] 問題の言いかえ

\(N\) を \(\frac{N+1}{2}\) で置き換えて葉が \(N\) 個である根付き二分木を考えることにします。

\(2\) つの子頂点について左右の区別をつける根付き二分木 \(T\) の各頂点に区間 \([L,R]\) を以下の条件を満たすように書き込むことを考えます。

• 頂点 \(v\) に書き込まれた区間は頂点 \(v\) の子孫に書き込まれたすべての区間と共通部分を持つ
• 頂点 \(v\) の左の子頂点の子孫に書き込まれた区間 \([L,R]\) と右の子頂点の子孫に書き込まれた区間 \([L',R']\) について、 \(R<L'\) が成り立つ

区間を書き込んだ後、\(L\) の昇順に \(1,2,\dots,N\) のラベルを付けることで条件を満たす整数組の列が得られます。このようにして得られた整数組の列について、 \(3\) 番目の条件を満たす \(T\) の構築を考えます。根にあたる区間はすべての区間と共通部分を持つ区間であり、これは一意です。残りの区間の左右の部分木への振り分け方も一意であるため、条件を満たす \(T\) は一意であることが帰納的にわかります。つまり、同じ整数組の列が \(2\) 回以上重複して作られることはありません。

以上より葉が \(N\) 個存在するすべての順序付き根付き二分木 \(T\) に対する区間の書き込み方の総和を求めればいいです。

[2] 区間の書き込み方の数え上げ

\(dp[v]:\) 頂点 \(v\) を根とする部分木内に区間を書き込む際、区間内の \(L,R\) の大小関係として考えられるものの数

を挿入dpで計算します。\(dp[\)根\(]\) が答えです。

\(v\) の左の子頂点、右の子頂点を \(c_{left},c_{right} \) とします。\(v\) を根とする部分木の頂点に区間を書き込む際、 \(L_v,R_v\) 以外の \(L,R\) の大小関係として考えられるのは \(dp[c_{left}] \times dp[c_{right}]\) 個です。これに条件を満たすように \(L_v,R_v\) を挿入する方法を考えれば \(dp[v]\) が求まります。これは \(v\) の子孫に書き込まれた区間の \(L,R\) の最大値、最小値を \(L_{max},R_{min}\) とおくと

\(dp[v]=dp[c_{left}] \times dp[c_{right}] \times \) \((\)部分木内の \(L\) のうち、\(L<R_{min}\) を満たす \(L\) の個数\(+1) \times \) \((\)部分木内の \(R\) のうち、\(L_{max} < R\) を満たす \(R\) の個数\(+1)\)

となります。ここで、 \((\)部分木内の \(L\) のうち、\(L<R_{min}\) を満たす \(L\) の個数\()\) は頂点 \(v\) から左の子をたどり続けることで到達できる頂点（ \(v\) を含まない）の数に等しいことが帰納的に示せます。\((\)部分木内の \(R\) のうち、\(L_{max} < R\) を満たす \(R\) の個数\()\) についても同様です。

すると \(T\) に対する区間の書き込み方の数は、下図のように \(N\) 個の葉から親へ（左右について）同じ方向にたどれるだけたどったパスを考え、それらの長さが \(k_i\) のとき、 \(\prod_{i=1}^N (k_i+1)!\) と求まります。例えば下図の二分木への区間の書き込み方の数は \((3+1)!\times (1+1)! \times (1+1)! \times (2+1)! \times (1+1)! \times (2+1)! = 6912\) 個と求まります。

[3] 順序木への対応付けによる答えの計算

[2] で考えた二分木上の \(N\) 個のパスについて、これらを頂点とみなし、\(2\) 本のパスが頂点を（ただ \(1\) つ）共有するときに隣接するとみなしたグラフをつくります。このグラフは木になっており、

• 最も左側のパスと最も右側のパスに対応する頂点を結ぶ辺を根とする
• パスの交わる頂点の深さで順序をつける

ことで順序木になっています。逆に、任意の辺を根とする順序木に対してこのような根付き二分木は一意に復元することができます。

さらに、各パスの長さは頂点の次数に等しくなっています。

よって問題はすべての（辺を根とした）順序木に対する、各頂点の次数 \(d\) に対する \((d+1)!\) の総積の総和を求めよ、という問題に言い換えられます。

この問題を解くため、ラベル付き順序木に対して数えて最後に \(N!\) で割って答えを求めることにします。頂点 \(i\) の次数が \(d_i\) であるような順序木は \(2(N-1)!\) 個存在するので答えは

\[[x^{2N-2}] \frac{2}{N} \left(\sum_{d=1}^{N} (d+1)! x^d\right)^N\]

になります。

順序木の個数の証明

各頂点に \(1\) から \(d_i-1\) の番号が付いた穴と特別な穴をつけ、

• 「穴と特別な穴を \(1\) つ選び辺で結ぶ」を \(N-2\) 回繰り返す
• 特別な穴が残っている \(2\) 頂点を左右をつけて辺を張り、この辺を根とする

という手順を踏むことで順序木が作れます。

\(i\ (1\leq i \leq N-2)\) 回目の手順で選べる穴の数は \(N-2-i\) 個であり、残っている \(N+1-i\) 個の特別な穴のうち、選べないのは \(1\) 個だけなので、 \(N-2\) 回の手順として考えられるのは \((N-2)! \times (N-1)!\) 個です。最後の手順は左右の付け方で \(2\) 通り考えられます。

根以外の辺が追加される順番を考えると、同じ順序木が \((N-2)!\) 回生成されるので、順序木の種類数は \(\frac{2 \times (N-2)! \times (N-1)!}{(N-2)!}=2 \times (N-1)!\) となります。

[4] \(4\) 番目の条件を考慮する

以上の議論を踏まえて \(4\) 番目の条件を考慮した問題を考えます。

まず \(L_i+1=R_i\) を満たす区間は葉にしか書き込めません。\(L_i+1=R_i\) を満たす区間を書きこむ葉を固定します。すると 区間の書き込み方の計算を[2] で述べたようなパスに分解して考えた際、葉に書き込む区間の種類によって

• 葉の \(L,R\) の間に \(L_v,R_v\) を挿入してはならない
• 最終的に葉の \(L,R\) の間になんらかの \(L_v,R_v\) が挿入されていなければならない

のどちらか片方の条件が付加されます。 \(1\) 番目の条件を満たす挿入の方法は \((k+1)!\) ではなく \(k!\) 通りになります。同様に、 \(2\) 番目の条件を満たす挿入の方法は \((k+1)!-k!\) 通りになります。

よって問題の答えは

\[[x^{2N-2}] \frac{2}{N} \ _{N}C_K\left(\sum_{i=1}^{N} d!x^d\right)^K\left(\sum_{d=1}^{N} ((d+1)!-d!)x^d\right)^{N-K}\]

となります。

これは畳み込みと二分累乗法を用いることで \(O(N\log^2N)\) で計算することができます（fps_powを用いると \(O(N\log N)\) で計算することもできます）。