Let interval \([l, r)\) denote the contiguous subsequence formed by the \(l\)-th, \((l+1)\)-th, \(\ldots\), \((r-1)\)-th elements of \(A\), and its length be \(r-l\). Intervals \([i, i+N)\) and \([j, j+N)\) are said to intersect when \(|i-j| \leq N\) (note that this includes the case \(|i - j| = N\)).

Consider the set \(R = \lbrace [1, N+1), [2, N+2), \ldots, [2N+1, 3N+1) \rbrace\) of all intervals of length \(N\). For a subset \(S \subseteq R\), let \(f(S)\) defined as

the number of sequences \(A\) where every interval in \(S\) constitutes a permutation of \((1,2,\ldots,N)\), multiplied by \((-1)^{|\mathcal{S}|}\).

From the inclusion-exclusion principle, the answer to the problem is \(\sum_{S \in 2^R} f(S)\).

If \(S = \emptyset\), then \(f(S) = (3N)! / (3!)^N\). Below, we consider the case \(S \neq \emptyset\).

A set of intervals \(S \subseteq R\) is said to form a group when for any two intervals \(a\) and \(b\) in \(S\), there is a sequence \(a = r_0, r_1, \ldots, r_k = b\) of intervals in \(S\) such that \(r_{i-1}\) and \(r_i\) intersect for every \(i = 1, 2, \ldots, k\). Also, let the length of a group \(S\) be the length of the interval that is the union of all intervals in \(S\).

Among the elements \(S\) of \(2^R \setminus \lbrace \emptyset \rbrace\), let \(\mathcal{P}\) be the set of those \(S\) such that some interval in \(S\) intersects all intervals in \(S\), and \(\mathcal{Q}\) be the set of the other \(S\). We will independently find \(\sum_{S \in \mathcal{P}} f(S)\) and \(\sum_{S \in \mathcal{Q}} f(S)\).

(1) Finding \(\sum_{S \in \mathcal{P}} f(S)\)

We fix \(S \in \mathcal{P}\), and let \(N+L\) be the length of \(S\) and \(l_0 < l_1 < l_2 < \cdots < l_k = l_0+L\) be the left ends of the intervals in \(S\). Now, to obtain \(A\) such that \([l_0, l_0+N), [l_1, l_1+N), \ldots, [l_k, l_k+N)\) are all permutations of \((1,2,\ldots,N)\), we first do the following:

• determine \([l_0, l_0+N)\) to be a permutation of \((1,2,\ldots,N)\) (\(N!\) ways),
• determine \([l_0+N, l_1+N)\) to be a permutation of \([l_0, l_1)\) (\((l_1-l_0)!\) ways),
• determine \([l_1+N, l_2+N)\) to be a permutation of \([l_1, l_2)\) (\((l_2-l_1)!\) ways),
• \(\cdots\),
• determine \([l_{k-1}+N, l_k+N)\) to be a permutation of \([l_{k-1}, l_k)\) (\((l_k-l_{k-1})!\) ways).

From \(S \in \mathcal{P}\), the above method guarantees that each integer from \(1\) to \(N\) occurs at most three times in \(A\). FInally, we should determine the \(2N-L\) elements outside \(S\) (let \(\rho(2N-L)\) be the number of ways to do this). Thus,

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

and taking the sum over all \(S \in \mathcal{P}\) yields:

\[\sum_{S \in \mathcal{P}} f(S) = -N! \sum_{L = 0}^{2N} \rho(2N-L) \sum_{\substack{S \in \mathcal{P},\\ S \text{ has length } N+L}} \prod_{i = 1}^k -(l_i-l_{i-1})!.\]

Here, let \(\mathcal{R}_1\) be the set of \(S \subseteq R\) such that all intervals in \(S\) form a single group. By definition, \(\mathcal{P} \subseteq \mathcal{R}_1\), so:

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

Now, consider the sum of the following over all sequences consisting of integers between \(1\) and \(N\) and totaling \(L\):

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

Then, the first term on the right-hand side of formula (1) can be found as:

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

(the coefficient \(2N-L+1\) comes from the number of ways to choose the position \(l_0\) of the left end of \(S\)). By finding the inverses of formal power series, \(w(0), w(1), \ldots, w(2N)\) can be found together in \(O(N \log N)\) time.

Now, we just need to find the second term on the right-hand side of formula (1). Let us fix an interval \(S \in \mathcal{R}_1 \cap \mathcal{Q}\) of length \(N+L\), and let \([u, u+N)\) and \([v, v+N)\) be the leftmost and rightmost intervals in \(S\), respectively. It follows from \(S \in \mathcal{Q}\) and the length of \(A\) being \(3N\) that every interval in \(S\) intersects exactly one of \([u, u+N)\) and \([v, v+N)\). Now, let \(U\) and \(V\) be the group formed by all intervals in \(S\) intersecting \([u, u+N)\) and the group formed by all intervals in \(S\) intersecting \([v, v+N)\), respectively. Also, let \(u = u_0 < u_1 < u_2 < \cdots < u_k = u_0+x\) and \(v = v_0 < v_1 < v_2 < \cdots < v_{k'} = v_0+y\) be the left ends of the intervals in \(U\) and \(V\), respectively. Moreover, let \(z = v_0-(u_k+N)\) be the length of the intersection of \(U\) and \(V\), and we have \(N+x+y-z = L\). Furthermore, it follows from \(S \in \mathcal{R}_1 \cap \mathcal{Q}\) that \((x, y, z) \in \lbrace (x', y', z') : 0 \leq x' < N, 0 \leq y' < N, 0 < z' < \min(x, y) \rbrace \eqqcolon P\).

We want to find:

\[ \begin{aligned} \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ S \text{ has length } N+L}} \prod_{i = 1}^k -(l_i-l_{i-1})! &= \sum_{\substack{S \in \mathcal{R}_1 \cap \mathcal{Q},\\ S \text{ has length } 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 \text{ has length } 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} \]

(the coefficient \(2N-L+1\) comes from the number of ways to choose the position \(l_0\) of the left end of \(S\)). To do this, we want to add \((N-z)!w(x)w(y)\) to \(B_{x+y-z}\) for all \((x, y, z) \in P\) fast enough.

Let us achieve this by divide-and-conquer. Consider adding \((N-z)!w(x)w(y)\) to \(B_{x+y-z}\) for all \((x, y, z) \in P\) such that \(l \leq x, y, z < r\). Let \(m=(l+r)/2\), and we have three cases.

• If \(x, y, z < m\) or \(m \leq x, y, z\): we can solve this recursively.
• If \(z < m \leq \min(x,y)\): FFT can achieve this in \(O((r-l) \log (r-l))\) time.
• If \(z < \min(x,y) < m \leq \max(x,y)\): from the symmetry of \(x\) and \(y\), it is enough to achieve the case \(x < y\). First convolute \(z\) and \(x\) by FFT, then extract the part with \(x > z\) from the result and convolute it with \(y\) by FFT to achieve this in \(O((r-l )\log (r-l))\) time.

(2) Finding \(\sum_{S \in \mathcal{Q}} f(S)\)

We fix \(S \in \mathcal{Q}\), and similarly to the argument above, we divide the intervals in \(S\) into \(U\), the group of intervals intersecting the leftmost interval \([u, u+N)\), and \(V\), the group of intervals intersecting the rightmost interval \([v, v+N)\). Let \(u = u_0 < u_1 < u_2 < \cdots < u_k = u_0+x\) and \(v = v_0 < v_1 < v_2 < \cdots < v_{k'} = v_0+y\) be the left ends of the intervals in \(U\) and \(V\), respectively. Also, let \(z = v - (u+N)\) be the distance between \([u+N)\) and \([v, v+N)\).

Now, to obtain \(A\) where every interval in \(S\) constitutes a permutation of \((1,2,\ldots,N)\), first note that each of \([u, u+N)\) and \([v, v+N)\) should constitute a permutation, and determine the \(N\) elements in neither of them to be a permutation (\(N!\) ways)$.

Then, for the \(U\) side,

• determine \([u_k, N)\) to be a permutation of the elements not in \([N, N+x)\) (\((N-x)!\) ways),
• determine \([u_{k-1}, u_k)\) to be a permutation of \([u_{k-1}+N, u_k+N)\) (\((u_k-u_{k-1})!\) ways),
• \(\cdots\)
• determine \([u_0, u_1)\) to be a permutation of \([u_0+N, u_1+N)\) (\((u_1-u_0)!\) ways),

and similarly for the \(V\) side,

• determine \([u_0+N+z, v_0+N)\) to be a permutation of the elements not in \([u_0+N, u_0+N+z)\) (\((N-y)!\) ways),
• determine \([v_0+N, v_1+N)\) to be a permutation of \([v_0, v_1)\) (\((v_1-v_0)!\) ways),
• \(\cdots\)
• determine \([v_{k'-1}, v_{k'})\) to be a permutation of \([v_{k'-1}+N, v_{k'}+N)\) (\((v_{k'}-v_{k'-1})!\) ways).

The number of ways to do this is:

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

Since \(S \in \mathcal{Q}\), the valid ranges for \(x, y, z\) are \(0 \leq x < z, 0 \leq y < z, 1 \leq z \leq N\), respectively, so we get:

\[\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)!\]

(the coefficient \(N-z+1\) comes from the number of ways to choose the position \(u_0\) of the left end of \(S\)).

The divide-and-conquer + FFT part is the bottleneck, and the total time complexity is \(O(N \log^2N)\).