\(s,t\) の先頭には \(1\) から \(N\) が \(2\) 回ずつ登場することから、\(s_i\) の先頭の項は \((a_i+1)/2\) （小数点以下切り捨て）と求まります。このとき、先頭の項に重複がある場合は \(s,t\) の生成の規則を満たさないので、明らかに \(0\) 通りです。以下、先頭の項が全て異なる場合を考えます。

\(s_i\) の先頭と \(t_j\) の先頭（\(s_j\) の末尾）が同じ数字である組に対して、これらの間の順序は真ん中の項で決まります。ここで、\(N\) 個の数列が定まっているとして、それに対応する以下のような有向グラフを考えます。

• 頂点 \(1,2, ... , N\) を \(N\) 個の数列に対応させる。
• \(s_i\) の先頭と \(t_j\) の末尾が同じであるとき、\(a_i<b_j\) であれば \(i\) から \(j\) の向き、そうでなければ逆向きに辺を張る

このグラフの性質を考えます。

まず、条件より各頂点の次数は \(2\) になります。すなわち、各連結成分はループになります。また、自己ループを含むことはあり得ません。その頂点に対応する数列は先頭と末尾が等しいということになり、\(s_i\) と \(t_i\) の順序が定義できないためです。

さらに、有向辺の向きは真ん中の項の大小を表しているため、これに矛盾しない真ん中の項の割り当てが存在する必要があります。これは、強連結な成分のサイズが全て 1 であれば、適当なトポロジカル順を取ることで可能です（自己ループがあると矛盾しますが、既に除かれているものとしています）。今回の連結成分は全てループであったため、全体が強連結である場合、すなわち全ての有向辺が同じ向きに揃っている場合、を除いて全てこの条件を満たします。

ここで、与えられた \(a\) により、各頂点 \(i\) の先頭の項に対応する辺の向きが決まっています。以下、上記の辺が \(i\) から出る向きである頂点 \(i\) を白い頂点、逆を黒い頂点と呼ぶことにします。 各連結成分について、同じ色の頂点のみからなっている場合、上記の考察より対応する数列を復元できません。逆に、異なる色の頂点が 1 つでも含まれていれば元の \(N\) 個の数列の復元が可能です。

この問題の数列 \(b\) は、上で考えたグラフのあり得る形状と一対一に対応するので、グラフの形状を数えます。\(b\) のうちすでに決まっている項を用いていくつかの頂点を繋げると、

• 白い頂点のみのパス \(W\) 個（孤立した頂点も含む）
• 黒い頂点のみのパス \(B\) 個（孤立した頂点も含む）
• 白い頂点と黒い頂点が混ざったパス \(G\) 個（以下、灰色のパスと呼びます）
• ループ

ができます。ループのうち一色の頂点しか含まないものがある場合は生成され得ないので、この場合の答えは \(0\) 通りです。そうでない場合、上記でできたパスを改めて頂点とみなし、白い頂点 \(W\) 個、黒い頂点 \(B\) 個、灰色の頂点 \(G\) 個と考えて、「白い頂点のみからなるループ、黒い頂点のみからなるループが存在しないようなループの作り方」を数えれば良いです。これは、以下のような方法で計算できます。

---

[計算方法1] 各色の極大なパスを繋ぐ方法

出来上がったグラフの中で、白い頂点からなるパス、黒い頂点からなるパスをそれぞれ極大になるように抽出し、それぞれ \(w\) 個、\(b\) 個であったとします。

最初に、灰色の頂点のみでいくつかのループを作っておき、後から白いパスや黒いパスを挿入することを考えます。灰色の頂点のループの作り方は

• \(G!\) 通り

です。続いて、白いパスを \(w\) 個作ります。\(W\) 個の頂点を一列に並べ、\(w-1\) 箇所で切断し、このとき \(w!\) 回同じものを数えてしまっているので補正すると、

• \(W! \times {}_{W-1}C_{w-1} / w!\) 通り
• ただし、\(W=0, w=0\) （白い頂点がない場合）に対しては \(1\) 通り

です。これを \(f(W,w)\) とします

次に、\(w\) 個のパスのうち、直後に黒い頂点に繋がっているものを \(s\) 個とすると、残りの \(w-s\) 個は灰色の頂点に繋げることになり、この繋げ方が

• \( {}_wC_{s} \times \lbrace b!/(b-s)!\rbrace \times\lbrace G!/(G-w+s)!\rbrace \) 通り

です。さらに、\(b\) 個の黒いパスについて、直後に繋がり得る頂点は白、灰で合計で \(G+s\) 個残っており、繋げ方は

• \((G+s)!/(G+s-b)!\) 通り

です。全てまとめて整理すると、

\[ (G!)^2 \times (G+s)! \times \Big\{ \frac{f(W,w)\times {}_wC_s}{(G-w+s)!} \Big\} \times \Big\{ \frac{f(B,b)\times b! }{(b-s)!\times (G+s-b)!} \Big\} \]

となります。この式を \(s, w, b\) について全て足し合わせれたものが答えです。

ここで、上の式は \(s\) と \(w\) にしか依存しない部分（中括弧の \(1\) つめ）と \(s\) と \(b\) にしか依存しない部分（中括弧の \(2\) つめ）の積に分解できるため、\(s\) を固定してそれぞれ和を先に計算し、\(s\) ごとに足し合わせていくことで、全体で \(O(N^2)\) で計算できます。

---

[計算方法2] 包除原理を用いる方法

\(W\) 個の白い頂点のうち、\(w_a\) 個に「同じ色のみのループに属する」という条件を課します（①）。さらに、そのような頂点以外のうち \(w_b\) 個が「①と同じループに属する」（②）とし、残りの \(w_c\) 個はそうではない（③）とします。

まず、白い頂点を①②③に分ける方法が

• \(W!/(w_a!w_b!w_c!)\) 通り

です。続いて、①のみでいくつかのループを作る方法が

• \(w_a!\) 通り

であり、その後に②をこのループのどこかに挿入していく方法が

• \((w_a+w_b-1)!/(w_a-1)!\) 通り
• \(w_a=0,w_b=0\) のときは例外で \(1\) 通り

あります。さらに、③と、黒の③に相当する頂点 \(b_c\) 個、灰色の頂点 \(G\) 個を用いていくつかのループを作ると

• \((w_c+b_c+G)!\) 通り

です。黒についてもグループ分けと①②のループの作り方は同様で、最後に

• 包除の係数 \((-1)^{w_a+b_a}\)

をかけ、整理すると

\[ \Big\{ (-1)^{w_a} \times \frac{W!\times (w_a+w_b-1)!}{w_b!\times w_c!\times (w_a-1)!} \Big\} \times \Big\{ (-1)^{b_a} \times \frac{B!\times (b_a+b_b-1)!}{b_b!\times b_c!\times (b_a-1)!} \Big\} \times (w_c+b_c+G)! \]

の総和を \(w_a, w_b, w_c, b_a, b_b, b_c\) について計算すればよいです。

ここで、\(w_c\) を固定したときの \(w_a, w_b\) に対するこれらのみに依存する部分（先頭の中括弧内の部分）の和を先に計算しておくと、あとは \(w_c, b_c\) の組について足し合わせればよく、どちらも \(O(N^2)\) で計算できます。

なお、この解法ではそれぞれの計算の部分を畳み込みの形にできるため、\(O(N\mathrm{log} N)\) で計算することもできます。

---

実装例（計算方法1）：https://atcoder.jp/contests/arc188/submissions/60033190