Mountain sequence
题号：NC258599
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
Special Judge, 64bit IO Format: %lld

题目描述

我们定义，当一个序列 a 存在一个 j 满足：

对于所有的 i 满足

a_i \leq a_{i+1} (1 \leq i \le j-1)

a_i \ge a_{i+1} (j \leq i \leq n-1)

那么我们称这个序列为山峰序列。

例如 [1,2,3,2,1]，[5,4,3,2,1]，[1,1,3] 是山峰序列。

而 [1,3,1,5,5,4]，[1,3,1,2]，就不是山峰序列。

现在 Antiamuny 给你了一个长度为 n 的序列，他想重排这个序列，并且他想知道有多少种方法可以使重排后的序列为山峰序列。

两种重排的方法不同当且仅当得到的序列不同，比如对于序列 [1,1,2]，只有 [1,1,2]，[1,2,1]，[2,1,1] 这三种不同的重排方法。

输入描述:

第一行包含一个整数 T (1 \leq T \leq 2 \times 10^5)，表示询问组数。

对于每组数据，第一行包含一个整数 n (1 \leq n \leq 10^5)，表示给定的序列长度。

第二行包含 n 个正整数 a_i (1 \leq a_i \leq 10^9)，表示给出的序列。

输入数据保证 \sum n \leq 2 \times 10^5

输出描述:

输出 T 行，每行一个整数，第 i 行表示第 i 个询问的答案。

因为答案可能过大，所以你需要输出答案对于 998244353 的余数。
示例1

输入

复制 
3
5
1 2 3 4 5
3
3 3 3
3
1 2 1

输出

复制 
16
1
3