#P18097. Sort

Sort

Sort

题目描述

给定长度为 nn 的排列 pp。每次操作独立地等概率选择整数 i∈[1,n]i\in[1,n],分别将 p[1..i]p[1..i] 与 p[i+1..n]p[i+1..n] 升序排序。当 i=ni=n 时,第二段为空,相当于将整个排列排序。

求排列首次变成完全升序所需的操作次数的期望,对 998244353998244353 取模。初始排列已经升序时,操作次数为 00。有理数 u/vu/v 在模意义下表示为 u⋅v−1u\cdot v^{-1}。

输入格式

第一行一个整数 TT。每组数据先输入 nn,下一行输入 p1,…,pnp_1,\ldots,p_n。

输出格式

每组数据输出一行,一个整数,表示期望的模值。

数据范围

1≤T≤1001\le T\le100,1≤n≤5001\le n\le500;pp 是 1,…,n1,\ldots,n 的排列。一个输入文件中所有 nn 之和不超过 20002000。

样例 1

输入

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

输出

748683267
2
670695427