反转排列

时间限制：2s
空间限制：1024MB

题目描述

给定整数 $N$ 和一个 $1$ 到 $N$ 的排列 $P=(P_1,P_2,\ldots,P_N)$。

对于任意一个 $1$ 到 $N$ 的排列 $Q$，考虑恰好执行一次下列操作后能够得到的、字典序最小的排列 $Q'$：

• 选择满足 $1\le l\le r\le N$ 的整数 $l,r$，反转连续段 $Q_l,Q_{l+1},\ldots,Q_r$。

求满足 $Q'=P$ 的排列 $Q$ 的数量。答案对 $998244353$ 取模。

你需要处理 $T$ 组测试数据。

输入格式

第一行输入整数 $T$。

随后依次输入每组测试数据。每组数据第一行输入整数 $N$，第二行输入 $N$ 个整数 $P_1,P_2,\ldots,P_N$。

输出格式

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

样例输入 1

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

样例输出 1

2
1
0
9

数据范围

对于所有数据：

• $1\le T$；
• $1\le N\le 5\times10^5$；
• $P$ 是 $1$ 到 $N$ 的排列；
• 单个测试点内所有测试数据的 $N$ 之和不超过 $5\times10^5$。