Permutation² Counting

题号：NC292148
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的序列 $a$ ，小苯想知道 $a$ 中有多少个子序列 $^\texttt{[1]}$ （不一定连续）是双排列 $^\texttt{[2]}$ ，请你数一数吧。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

【名词解释】
$\hspace{15pt}$ 子序列 $^\texttt{[1]}$ ：从原数组中删除任意个（可以为零、可以为全部）元素得到的新数组。

$\hspace{15pt}$ 双排列 $^\texttt{[2]}$ ：长度为 $2\times n$ 的双排列为两个长度为 $n$ 的排列 $^\texttt{[3]}$ 打乱顺序后得到的数组。
$\hspace{15pt}$ 排列 $^\texttt{[3]}$ ：长度为 $n$ 的排列是由 $1,2,\dots,n$ 这 $n$ 个整数、按任意顺序组成的数组（每个整数均恰好出现一次）。例如， $\{2,3,1,5,4\}$ 是一个长度为 $5$ 的排列，而 $\{1,2,2\}$ 和 $\{1,3,4\}$ 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个正整数 ，表示序列  的长度。
第二行  个正整数 ，表示序列 。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
输出一行一个整数，表示是 "双排列" 的子序列个数对  取模的值。

示例1

输入

复制

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

输出

复制

6
2

说明

对于第二组测试数据，有：
 和  两个子序列是双排列。