Talk Event
有 N 人参加活动。每人持有 1,2,3,4 张票中的一种数量,其中持有 i 张票的人数为 Ti,且 T1+T2+T3+T4=N。
从中选择恰好 K 人,要求这些人持有的票数总和不超过 X,并且加入任意一名尚未选中的人后,票数总和都会超过 X。
持有相同票数的人不作区分:一种方案只由四个整数 (t1,t2,t3,t4) 决定,其中 ti 表示选中了多少名持有 i 张票的人。因此必须满足 0≤ti≤Ti,并且 t1+t2+t3+t4=K。
求方案数量,对 998244353 取模。如果所有人都已经选中,“加入任意一名未选中的人”的条件自然成立。
输入格式
第一行一个整数 T。每组测试两行:第一行三个整数 N,K,X,第二行四个整数 T1,T2,T3,T4。
输出格式
每组测试输出一行一个整数,表示方案数量对 998244353 取模的结果。
数据范围
1≤T≤104,1≤N≤250000000,1≤K≤N,1≤X≤109,Ti≥0,∑i=14Ti=N。所有输入均为整数。
样例 1
输入:
2
24 8 11
7 6 3 8
24 3 28
7 6 3 8
输出:
4
0