#P18021. Palindrome and Permutation

Palindrome and Permutation

Palindrome and Permutation

给定一个长度为 NN 的整数数组 AA。你希望将它变成回文数组:对所有 1≤i≤N1\le i\le N,都有 Ai=AN+1−iA_i=A_{N+1-i}。

对于 1,2,…,N1,2,\ldots,N 的一个排列 PP,依次进行以下过程。第 ii 步必须选择恰好一个下标 jj,将当前的 AjA_j 改成 PiP_i。不同步骤允许选择相同的下标。数组第一次变成回文时立即停止;若始终未变成回文,则进行完 NN 步后停止。

设 f(A,P)f(A,P) 为在最优选择每一步修改下标的情况下,使数组成为回文所需的最少步数。如果初始数组已经是回文,规定 f(A,P)=0f(A,P)=0;如果全部 NN 步后仍无法变成回文,规定 f(A,P)=N+1f(A,P)=N+1。

求所有排列 PP 对应的 f(A,P)f(A,P) 之和,答案对 998244353998244353 取模。

输入格式

第一行一个整数 TT,表示测试用例数。每组数据第一行一个整数 NN,第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

每组数据输出一行一个整数,表示所求的和对 998244353998244353 取模后的结果。

数据范围

1≤T≤1051\le T\le10^5,1≤N≤50001\le N\le5000,1≤Ai≤N1\le A_i\le N。所有测试用例的 N2N^2 之和不超过 500025000^2。

样例 1

输入

4
3
1 2 3
4
2 3 3 2
6
4 6 4 6 4 6
10
1 5 2 10 2 6 3 1 10 2

输出

8
0
5040
31363200