#P17907. Play It by Ear
Play It by Ear
题目描述
有 张不同的牌,编号为 到 。初始牌堆是这 张牌的均匀随机排列。你取出顶部 张作为手牌,剩余牌堆的顺序不可见。
每轮必须从当前手牌中选择一张,放到牌堆底部,再抽取牌堆顶部的一张。因此手牌数量始终是 。
任务序列为 ,必须依次完成。当前任务为 时,打出编号为 的牌才能完成它。一次出牌至多完成一个任务;提前打出的牌不会计入以后任务。你事先知道整个任务序列。
你采用纯策略:每次选择仅依赖初始手牌、已经打出和抽到的牌、当前任务等可观测历史;相同历史必须作出相同选择,不能利用未看到的牌堆顺序。
求所有纯策略中,完成全部任务的最小期望轮数,并对 取模。随机性仅来自初始洗牌。
输入格式
第一行是 。每组包含两行:第一行为 ;第二行为 个整数 。
输出格式
每组输出一个整数。如果答案的最简分数为 ,输出唯一的 ,满足 。保证该值存在。
数据范围
,,,。所有组的 之和不超过 , 之和不超过 。
样例输入
3
2 1
1
3 7
2 5 1 2 6 2 1
1000 2
1116 1116
样例输出
249561090
299473317
748684517
样例说明
第一组的答案为 。