#P18033. Talk Event

Talk Event

Talk Event

有 NN 人参加活动。每人持有 1,2,3,41,2,3,4 张票中的一种数量,其中持有 ii 张票的人数为 TiT_i,且 T1+T2+T3+T4=NT_1+T_2+T_3+T_4=N。

从中选择恰好 KK 人,要求这些人持有的票数总和不超过 XX,并且加入任意一名尚未选中的人后,票数总和都会超过 XX。

持有相同票数的人不作区分:一种方案只由四个整数 (t1,t2,t3,t4)(t_1,t_2,t_3,t_4) 决定,其中 tit_i 表示选中了多少名持有 ii 张票的人。因此必须满足 0≤ti≤Ti0\le t_i\le T_i,并且 t1+t2+t3+t4=Kt_1+t_2+t_3+t_4=K。

求方案数量,对 998244353998244353 取模。如果所有人都已经选中,“加入任意一名未选中的人”的条件自然成立。

输入格式

第一行一个整数 TT。每组测试两行:第一行三个整数 N,K,XN,K,X,第二行四个整数 T1,T2,T3,T4T_1,T_2,T_3,T_4。

输出格式

每组测试输出一行一个整数,表示方案数量对 998244353998244353 取模的结果。

数据范围

1≤T≤1041\le T\le10^4,1≤N≤2500000001\le N\le250000000,1≤K≤N1\le K\le N,1≤X≤1091\le X\le10^9,Ti≥0T_i\ge0,∑i=14Ti=N\sum_{i=1}^4T_i=N。所有输入均为整数。

样例 1

输入:

2
24 8 11
7 6 3 8
24 3 28
7 6 3 8

输出:

4
0