#P18672. Classical Counting Problem
Classical Counting Problem
Classical Counting Problem
题目描述
为即将举行的一场比赛,一共提出了 道题。第 道题的初始分数为整数 。
共有 位评委为自己喜欢的题目投票。每位评委独立于其他评委,恰好选择 道不同的题目,并将所选每道题的分数增加 。不同评委可以选择相同的题目。
全部 位评委投票结束后,将题目按最终分数从高到低排序。对于某个 ,选取排序后的前 道题作为比赛题集。最终分数相同的题目可以任意排列,具体次序由比赛负责人决定。
在所有可能的投票结果、所有合法的 以及所有允许的同分排列下,一共能得到多少个不同的题集?输出答案对 取模的结果。如果存在某道题只属于两个题集中的一个,就认为这两个题集不同。题集非空, 并未固定为 。
输入格式
第一行包含测试用例数 ()。
每个测试用例第一行包含三个整数 ,分别表示题目数、评委数以及每位评委选择的题目数,满足 、、。
第二行包含 个整数 ,表示初始分数,满足 。
保证所有测试用例的 之和不超过 。
输出格式
对每个测试用例输出一行,包含可能题集数对 取模的结果。
样例输入 1
6
3 1 2
1 2 3
3 2 1
1 2 3
10 1 1
0 0 0 0 0 0 0 0 0 0
6 1 2
2 1 1 3 0 2
6 1 5
2 1 1 3 0 2
10 4 8
7 2 3 6 1 6 5 4 6 5
样例输出 1
5
6
1023
23
19
240
样例说明
第一组测试的全部可能题集为 、、、、。
第二组测试的全部可能题集为 、、、、、。
第三组测试中,任意非空题目子集都可以成为最终题集。