题目描述

教育局这个季度拨下来一笔进修名额，交给程老师往下分。名额要分给几个教研组，组是按编号认的：同样是一组拿三个、另一组拿一个，把这两个数换个组来给，就算另一种分法；至于名额本身，一个个都长一个样，不编号也不排序，只看分完之后每个组名下有几个。名额必须一个不剩地分完，全都落到某个组头上。

每个组都向程老师报了一个数，那是这个组自己估摸的最低需求——分给它的名额不能低于这个数。程老师手上这一批一共有 $m$ 个名额，要分给 $n$ 个组，第 $i$ 个组报的数是 $a_i$。如果 $n$ 个组报的数加起来已经超过了 $m$，那这批名额就分不下去，程老师把这批的分法数记作 $0$。

这样的批次不止一批。程老师手上压着一摞单子，每张单子写着这一批的名额总数和这一批里每个组报的数，他要一张一张地算出分法有多少种。数目可能很大，他只要对 $998244353$ 取模之后的结果。

现在给出这一摞单子，请你帮程老师算出每一批的分法数。

输入格式

从文件 quota.in 中读入数据。

第一行一个正整数 $q$，表示单子的张数。

接下来 $q$ 批数据，每批两行：第一行两个整数 $n, m$，中间用一个空格隔开；第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，相邻两个整数之间用一个空格隔开。

输出格式

输出到文件 quota.out 中。

共 $q$ 行，每行一个整数，依次表示每一批的分法数对 $998244353$ 取模后的结果。

数据范围

对于所有测试数据，保证：

• $1 \le q \le 10^5$；
• $1 \le n \le 10$，$0 \le m \le 2000$，$0 \le a_i \le 2000$。

特殊性质 A：每一批里所有组报的数都是 $0$。

特殊性质 B：每一批都有 $n = 2$。

2
3 5
1 1 1
2 3
2 0

6
2

1
3 2
1 1 1

0

样例解释

样例 1 第一批：三个组报的数都是 $1$，先给每个组各留 $1$ 个，用掉 $3$ 个，还剩 $2$ 个名额可以随便分。这 $2$ 个名额落到三个组头上的方式有六种：全给第一个组、全给第二个组、全给第三个组、给前两个组各一个、给第一和第三个组各一个、给后两个组各一个。各自加上先前留的那 $1$ 个，六种分法依次是 $(3,1,1)$、$(1,3,1)$、$(1,1,3)$、$(2,2,1)$、$(2,1,2)$、$(1,2,2)$，共 $6$ 种。

样例 1 第二批：第一个组报的数是 $2$，第二个组报的是 $0$。第一个组至少要拿 $2$ 个，剩下的名额全归第二个组，于是分法只有 $(2,1)$ 与 $(3,0)$ 两种。

样例 2：三个组各报 $1$，加起来是 $3$，超过了这一批的 $2$ 个名额，分不下去，分法数记 $0$。