题目描述

给定正整数 $n$ 以及正整数序列 $a_1,a_2,\cdots, a_n$，其中 $a_i$ 表示第 $i$ 个点的颜色。求同时满足如下条件的大小为 $n$ 的简单无向图 $G$ 的个数：

1. 边之间没有公共端点。即 $G$ 是一匹配。

2. 对于任一条边它的两个端点的颜色相同。

3. 对两条不同的边 $e_1=(u_1,v_1) (u_1< v_1)$ 与 $e_2=(u_2,v_2) (u_2< v_2)$，若 $u_1< u_2< v_1< v_2$ 或 $u_2< u_1< v_2< v_1$ 则称 $e_1$ 与 $e_2$ 相交。满足 $e_1$ 与 $e_2$ 相交的无序对 $(e_1,e_2)$ 有偶数个。

由于答案可能很大，对 $998244353$ 取模。每个数据点有 $T$ 组数据。

输入格式

第一行输入一个正整数 $T$。接下来紧跟着 $T$ 组数据，两组数据之间会换一行。

每组数据的第一行是一个正整数 $n$，第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，两个正整数之间以一个空格隔开。

输出格式

$T$ 行，每行一个非负整数表示答案。

3
3
1 2 3
4
1 2 1 2
4
4 4 4 4

1
3
9

数据范围与提示

对于数据点 $1\sim 2$，$n\le 13$。

对于数据点 $3\sim 4$，$a_i$ 是全部相同的。

对于数据点 $5\sim 10$，$a_i\le 10$。

对于数据点 $11\sim 14$，$n\le 300$。

对于数据点 $15\sim 20$，$n\le 2000$。

对 $100\%$ 的数据，$1\le T\le 5, 1\le n\le 2000, 1\le a_i\le n$。