听说你们寒假马上有过完了,于是贵校要开始排课了,贵校共有 个班级。
对于其中一个班级 ,这个班级每天要上 节互不相同的课,一共有 节课可供选择,但这 节课不能随便安排,其中也有一些限制:
你需要求出每个班级排课的方案数除以 的余数。
注意:尽量使用加速读入或者快读避免超时
第1行包含一个正整数 ,表示贵校有的班级数。
1
第2行到第T+1行,每行包含四个整数,第i+1行的四个整数 ,,,,分别表示班级 可选的课程数,一天的课程数,不能在第一节上的课程数,不能在最后一节上的课程数。
2
T+1
i+1
输出T行,第i行表示班级 的排课方案数除以 的余数。
T
i
样例输入 1
1 3 2 0 1
样例输出 1
4
样例解释 1
设3节可选的课为a,b,c,其中c不能排在最后一节
3
a
b
c
4种排课表的方案分别为:ab,ba,ca,cb
ab
ba
ca
cb
样例输入 2
1 5 3 1 1
样例输出 2
39
样例输入 3
4 58 58 10 41 55 55 52 0 69 69 35 16 65 65 20 18
样例输出 3
684799781 726208648 640586838 361935207
所有测试点满足:
1 ~ 2
3 ~ 6
7 ~ 10
10 ~ 14
15 ~ 20
在测试点7 ~ 20中:
7 ~ 20