\(A\) の \(l, l+1, \ldots, r-1\) 番目の要素からなる連続部分列を区間 \([l, r)\) と呼び、その長さを \(r-l\) で定めます。 区間 \([i, i+N)\) と区間 \([j, j+N)\) は、\(|i-j| \leq N\) のとき、交わるということにします（ \(|i - j| = N\) のケースも含むことに注意してください）。

長さ \(N\) の区間全体からなる集合 \(R = \lbrace [1, N+1), [2, N+2), \ldots, [2N+1, 3N+1) \rbrace\) の部分集合 \(S \subseteq R\) に対して \(f(S)\) を、

\(S\) に含まれる全ての区間が順列であるような \(A\) の個数を、\((-1)^{|\mathcal{S}|}\) 倍したもの

と定めます。 包除原理より本問題の答えは \(\sum_{S \in 2^R} f(S)\) です。

\(S = \emptyset\) の場合は\( f(S) = (3N)! / (3!)^N\)です。 以下、\(S \neq \emptyset\) の場合を考えます。

区間の集合 \(S \subseteq R\) がグループであるとは、 \(S\) の任意の \(2\) 区間 \(a, b\) に対して、\(S\) の区間の列 \(a = r_0, r_1, \ldots, r_k = b\) であって全ての \(i = 1, 2, \ldots, k\) で \(r_{i-1}\) と \(r_i\) が交わるようなものが存在することをいいます。 また、グループ \(S\) に含まれる全ての区間の和集合として得られる区間の長さを、グループ \(S\) の長さとします。

\(2^R \setminus \lbrace \emptyset \rbrace\) の要素 \(S\) のうち、 \(S\) の全ての区間と交わる \(S\) の区間が存在するようなものの集合を \(\mathcal{P}\) 、 それ以外のものの集合を \(\mathcal{Q}\) とし、 \(\sum_{S \in \mathcal{P}} f(S)\) と \(\sum_{S \in \mathcal{Q}} f(S)\) をそれぞれ独立に求めます。

（１）\(\sum_{S \in \mathcal{P}} f(S)\) の計算

\(S \in \mathcal{P}\) を固定し、\(S\) の長さを \(N+L\) 、\(S\) の各区間の左端を \(l_0 < l_1 < l_2 < \cdots < l_k = l_0+L\) とおきます。 このとき、\([l_0, l_0+N), [l_1, l_1+N), \ldots, [l_k, l_k+N)\) が全て順列であるような \(A\) を得るには、まず、

• \([l_0, l_0+N)\) を順列になるように決め（ \(N!\) 通り）
• \([l_0+N, l_1+N)\) を \([l_0, l_1)\) の並べ替えになるように決め（ \((l_1-l_0)!\) 通り）
• \([l_1+N, l_2+N) \)を \([l_1, l_2)\) の並べ替えになるように決め（ \((l_2-l_1)!\) 通り）
• \(\cdots\)
• \([l_{k-1}+N, l_k+N)\) を \([l_{k-1}, l_k)\) の並べ替えになるように決めます（ \((l_k-l_{k-1})!\) 通り）。

\(S \in \mathcal{P}\) より、上の方法で決めた \(A\) には \(1\) から \(N\) までの各整数はそれぞれ \(3\) 回以下しか出現しないことが保証されます。 最後に \(S\) の外側の \(2N-L\) 個の要素を決め（ \(\rho(2N-L)\) 通りとおく）れば良いです。 よって、

\[f(S) = -N! \rho(2N-L) \prod_{i = 1}^k -(l_i-l_{i-1})!\]

であり、すべての \(S \in \mathcal{P}\) で和を取ると、

\[\sum_{S \in \mathcal{P}} f(S) = -N! \sum_{L = 0}^{2N} \rho(2N-L) \sum_{\substack{S \in \mathcal{P},\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})!\]

です。 ここで、\(S\) 全体が \(1\) つのグループをなすような \(S \subseteq R\) の集合を \(\mathcal{R}_1\) とおくと、定義より \(\mathcal{P} \subseteq \mathcal{R}_1\) ですので、

\[\sum_{\substack{S \in \mathcal{P},\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! = \sum_{\substack{S \in \mathcal{R}_1,\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! - \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! \tag{1} \]

です。 ここで、\(1\) 以上 \(N\) 以下の整数からなる総和 \(L\) の数列 \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)\) 全てにわたる下記の和

\[w(L) = \sum_{\lambda} \prod_{i = 1}^k -(\lambda_i)! = [x^L]\Big(\frac{1}{1 + \sum_{i = 1}^N i! x^i}\Big) \]

を考えると、式 (1) 右辺の第１項については、

\[\sum_{\substack{S \in \mathcal{R}_1,\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! = (2N-L+1) w(L)\]

と求まります（係数 \(2N-L+1\) は \(S\) の最左端の位置 \(l_0\) を選ぶ方法の個数に由来）。 形式的冪級数の逆元を求める操作によって、\(w(0), w(1), \ldots, w(2N)\) はまとめて \(O(N \log N)\) 時間で計算できます。

よって、あとは式 (1) 右辺の第2項が求まれば良いです。 長さ \(N+L\) の区間 \(S \in \mathcal{R}_1 \cap \mathcal{Q}\) を固定し、\(S\) の最左の区間を \([u, u+N)\) 、最右の区間を \([v, v+N)\) とします。 \(S \in \mathcal{Q}\) であることと \(A\) の長さは \(3N\) であることから、\(S\) のどの区間も \([u, u+N)\) と \([v, v+N) \)のちょうど一方と交わります。 そこで、\(S\) の区間のうち \([u, u+N)\) に交わる区間全体がなすグループを \(U\) 、\([v, v+N)\) に交わる区間全体がなすグループを \(V\) とし、 \(U\) の各区間の左端を \(u = u_0 < u_1 < u_2 < \cdots < u_k = u_0+x\) 、\(V\) の各区間の左端を \(v = v_0 < v_1 < v_2 < \cdots < v_{k'} = v_0+y\) とおきます。 また、\(U\) と \(V\) の共通部分の長さを \(z = v_0-(u_k+N)\) とおくと \(N+x+y-z = L\) が成り立ちます。 さらに、\(S \in \mathcal{R}_1 \cap \mathcal{Q}\) より、\((x, y, z) \in \lbrace (x', y', z') : 0 \leq x' < N, 0 \leq y' < N, 0 < z' < \min(x, y) \rbrace \eqqcolon P\) です。

求めたいのは、

\[ \begin{aligned} \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ Sの長さはN+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! &= \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ Sの長さはN+L}} (v_0-u_k)!\prod_{i = 1}^k -(u_i-u_{i-1})! \prod_{i = 1}^{k'} -(v_i-v_{i-1})!\\ &= \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ Sの長さはN+L}} (N-z)! w(x) w(y)\\ &= (2N-L+1) \sum_{\substack{(x, y, z) \in P \\ N+x+y-z = L}} (N-z)! w(x) w(y) \end{aligned} \]

です（係数 \(2N-L+1\) は \(S\) の最左端の位置 \(u_0\) を選ぶ方法の個数に由来）が、これを求めるには全ての \((x, y, z) \in P\) について、\(B_{x+y-z}\) に \((N-z)!w(x)w(y)\) を足し込むという操作が十分高速にできれば良いです。

これを分割統治によって実現します。 \(l \leq x, y, z < r\) を満たす \((x, y, z) \in P\) の全てについて「 \(B_{x+y-z}\) に \(w(x)w(y)(N-z)!\) を足し込む」という操作を実現することを考えます。 \(m=(l+r)/2\) とおき、\(3\) つのケースに場合分けします。

• \(x, y, z < m\)、または、\(m \leq x, y, z\) のケース：再帰的に解くことができます。
• \(z < m \leq \min(x,y)\) のケース：FFT によって \(O((r-l) \log (r-l))\) 時間で実現できます。
• \(z < \min(x,y) < m \leq \max(x,y)\) のケース： \(x\) と \(y\) の対称性より \(x < y\) の場合が実現できれば良いです。 まず \(z\) と \(x\) に関して FFT による畳み込みを行い、その結果から \(x > z\) の部分だけを取り出したものを、FFT によって \(y\) と畳み込むことで、\(O((r-l )\log (r-l))\) 時間で実現できます。

（２）\(\sum_{S \in \mathcal{Q}} f(S)\) の計算

\(S \in \mathcal{Q}\) を固定し、先程の議論と同様に、\(S\) の区間を最左の区間 \([u, u+N)\) に交わる区間のグループ \(U\) と、最右区間 \([v, v+N)\) に交わる区間のグループ \(V\) にわけ、\(U\) の各区間の左端を\(u = u_0 < u_1 < u_2 < \cdots < u_k = u_0+x\) 、\(V\) の各区間の左端を \(v = v_0 < v_1 < v_2 < \cdots < v_{k'} = v_0+y\) とおきます。 また、\([u+N)\) と \([v, v+N)\) の距離を \(z = v - (u+N)\) とおきます。

このとき、\(S\) の区間が全て順列である \(A\) を得るには、 まず、\([u, u+N)\) と \([v, v+N)\) がそれぞれ順列になるべきことに着目し、そのどちらにも含まれない要素 \(N\) 個を、順列になるように決めます（ \(N!\) 通り）。

そして、\(U\) 側について、

• \([u_k, N)\) を \([N, N+x)\) に含まれない要素の並べ変えで決め（ \((N-x)!\) 通り）
• \([u_{k-1}, u_k)\) を \([u_{k-1}+N, u_k+N)\) の並べ変えで決め（ \((u_k-u_{k-1})!\) 通り）
• \(\cdots\)
• \([u_0, u_1)\) を \([u_0+N, u_1+N)\) の並べ変えで決め（ \((u_1-u_0)!\) 通り）、

\(V\) 側についても同様に、

• \([u_0+N+z, v_0+N)\) を \([u_0+N, u_0+N+z)\) に含まれない要素の並べ変えで決め（ \((N-y)!\) 通り）
• \([v_0+N, v_1+N)\) を \([v_0, v_1)\) の並べ変えで決め（ \((v_1-v_0)!\) 通り）
• \(\cdots\)
• \([v_{k'-1}+N, v_{k'}+N)\) を \([v_{k'-1}, v_{k'})\) の並べ変えで決め（ \((v_{k'}-v_{k'-1})!\) 通り）

れば良いので、その方法の個数は

\[ N!(N-x)!(N-y)!\prod_{i = 1}^k -(u_i-u_{i-1})! \prod_{i = 1}^{k'} -(v_i-v_{i-1})! \]

であり、\(S \in \mathcal{Q}\) から \(x, y, z\) のとり得る範囲はそれぞれ \(0 \leq x < z, 0 \leq y < z, 1 \leq z \leq N\) なので、

\[\sum_{S \in \mathcal{Q}} f(S) = N! \sum_{z = 1}^N (N-z+1) \sum_{x = 0}^{z-1} \sum_{y = 0}^{z-1} w(x)w(y)(N-x)!(N-y)!\]

を得ます（係数 \(N-z+1\) は \(S\)の最左端の位置 \(u_0\) を選ぶ方法の個数に由来）。

分割統治 + FFT のパートがボトルネックとなり、全体の計算量は \(O(N \log^2N)\) 時間です。