小苯的小球分组

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

题目描述

$\hspace{15pt}$ 小苯有 $n$ 个小球，其中第 $i$ 个小球的颜色为 $a_i$ 。从其中取出一些小球，组成一个小球集合 $\Bbb S$ 。定义小球集合 $\Bbb S$ 的函数 $f(\Bbb S)$ ，表示将小球集合 $\Bbb S$ 分为若干组，满足以下所有条件的最少分组个数：
$\hspace{23pt}\bullet$ 每组最多有 $2$ 个球；
$\hspace{23pt}\bullet$ 组内有 $2$ 个球的组，这 $2$ 个球的颜色不同。
$\hspace{15pt}$ 现在小苯希望你求出这 $n$ 个小球的所有非空子集（按位置区分）所对应的 $f$ 函数值之和。由于答案可能很大，请将答案对 $998\,244\,353$ 取模后输出。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下： 
第一行输入一个整数 ，表示小球的总个数。 
第二行输入  个整数 ，表示每个小球的颜色。 

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

输出描述:

对于每一组测试数据，新起一行。输出一个整数，表示所有子序列的  函数值之和。由于结果可能很大，请将答案对  取模后输出。

示例1

输入

复制

输出

复制

9
20
55

说明

对于第一组测试数据，共有  个不同的非空子序列，其对应  值如下：
， 为 ；
， 为 ；
， 为 ；
， 为 ；
， 为 ；
， 为 ；
， 为 。 
因此总和为：。