A4919 | 偶数Ⅰ

数据范围

- $1\le t\le 3 \times 10^3$
- $3\le n\le 3 \times 10^3$


经过严谨的数学证明可知，该期望值的答案能够表示为最简分数形式 $\dfrac{p}{q}$，其中 $p$ 和 $q$ 均为整数，并且 $q$ 满足 $q\not\equiv 0\pmod{998244353}$。请你计算并输出一个满足 $p\cdot q^{-1}\mod 998244353$ 的整数。也就是说，输出一个整数 $x$，使得 $0\leq x\lt 998244353$ ，并且 $x\cdot q\equiv p\pmod{998244353}$。

提示：依据费马小定理，有 $q^{-1}\equiv q^{998244351}\pmod{998244353}$。

样例解释:
当 $n$ 的值为 $3$ 时。 $(a,b,c)$ 的组合一共有 6 种。如 $(1 , 3 ,5)$ , $(1 ,5 ,3 )$ , $(3,1,5)$ , $(3,5,1)$ , $(5,3,1)$ , $(5,1,3)$ ,他们通过函数进行计算的结果分别为 $242$ ,$124$ , $124$ , $2$ , $2$ , $124$ ,其美丽值的分别为 $1$ , $2$ , $1$ , $1$ , $1$ , $2$ 。因此美丽值的期望为 $\dfrac{4}{3}$ ，进行相应的运算之后为 $332748119$ 。