题目描述

Alice 有一个长度为 $n$ 的排列 $p$，请帮她求出 $p$ 有多少个非空子序列满足逆序对数与 $p$ 本身的逆序对数相等。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的值。

一个长度为 $n$ 的排列是一个包含 $1\sim n$ 各一次的数组。

数组 $a_{1\dots n}$ 的逆序对数是满足 $1\leq i<j\leq n,a_i>a_j$ 的 $(i,j)$ 对数。

数组 $a$ 的子序列是从其中删除若干元素，将剩余元素按顺序拼接起来所得到的序列。

输入格式

第一行一个整数 $T$ 表示数据组数，对于每组数据：

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1,p_2,\dots,p_n$。

输出格式

对于每组数据，输出一行一个整数表示答案。

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

31
2

样例解释 1

对于第一组数据，任何非空子序列的逆序对数都是0，与p的逆序对数相等，答案为2^5-1=31。 对于第二组数据，p的逆序对数是3，子序列[3,1,2,4,6,5],[3,1,2,6,5]的逆序对数与其相等。

数据范围

对于 $30\%$ 的数据，$\sum n\leq 20$。

对于 $60\%$ 的数据，$\sum n\leq 5000$。

对于 $100\%$ 的数据，$1\leq T\leq 1000$，$2\leq n\leq 10^5$，$\sum n\leq 5\times 10^5$。