You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

$Diana$ 正在和大家玩你画我猜。

出于一些原因，小 $z$ 预知了 $Diana$ 将会画一个有 $n$ 个点的大根堆：一棵树，每个点被从 $1$ 到 $n$ 编号，而每个点的编号大于其所有孩子的编号。

小 $z$ 还预知了对于第 $i$ 个点，其度数（孩子的个数）不超过 $d_i$。

然而，小 $z$ 只会猜答案。它想知道它猜对的概率，所以想请你帮忙计算所有符合条件的堆的方案数。

由于小 $z$ 大脑的容量极其有限，所以你只需要告诉它答案对 $998244353$ 取模后的答案。

子树之间是有序的。即，两个方案不同当且仅当存在一个点在两个方案中的孩子组成的有序序列不同。

输入格式

从文件 $heap.in$ 中读入数据。

本题包含多组测试数据。

第一行一个正整数 $T$ ，表示数据组数。

接下来 $2T$ 行，每两行代表一组测试数据。对于每组测试数据：

第一行一个正整数 $n$ ，表示 $Diana$ 画的堆的点数。

第二行 $n$ 个整数 $d_1,d_2,...,d_n$ ，表示每个点度数的上限。

输出格式

输出到文件 $heap.out$ 中。

共 $T$ 行，每行一个非负整数表示答案对 $998244353$ 取模的结果。

样例 1 输入：

3
4
0 1 2 2
4
0 1 2 3
10
0 1 2 2 3 2 3 4 2 4

样例 1 输出：

9
15
8285157

样例 1 解释：

对于第一组测试数据，存在以下 $9$ 种方案：

样例 2 ：

见右侧文件的 $heap2.in$ 与 $heap2.ans$ 。

数据范围

对于所有测试数据，保证 $1≤T≤5，1≤n≤5000，0≤d_i<i$ 。

每个测试点的具体限制见下表：