#P18021. Palindrome and Permutation
Palindrome and Permutation
Palindrome and Permutation
给定一个长度为 的整数数组 。你希望将它变成回文数组:对所有 ,都有 。
对于 的一个排列 ,依次进行以下过程。第 步必须选择恰好一个下标 ,将当前的 改成 。不同步骤允许选择相同的下标。数组第一次变成回文时立即停止;若始终未变成回文,则进行完 步后停止。
设 为在最优选择每一步修改下标的情况下,使数组成为回文所需的最少步数。如果初始数组已经是回文,规定 ;如果全部 步后仍无法变成回文,规定 。
求所有排列 对应的 之和,答案对 取模。
输入格式
第一行一个整数 ,表示测试用例数。每组数据第一行一个整数 ,第二行 个整数 。
输出格式
每组数据输出一行一个整数,表示所求的和对 取模后的结果。
数据范围
,,。所有测试用例的 之和不超过 。
样例 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