一共有q+1个人跟你抢票,有些人可以抢两种票,有一些只能抢第二组票,求出你能抢到票的排列组合数量
预处理组合数和排列数: 由于数据量较大(最大到3000),可以使用杨辉三角预处理出组合数 C(n, m) 和排列数 A(n, m),以便在后续计算中快速查询。
分配抢票玩家: 将抢票玩家分为两类:可以抢两档票的玩家(天数 <= t)和只能抢第二档票的玩家(天数 > t)。统计这两类玩家的数量分别为 n1 和 n2。
枚举抢票情况:
米小游是一位《原神》的全勤玩家,但她却抢不到《原神FES》的门票,因此决定开发一款有利于全勤玩家的抢票系统。
新的抢票系统如下:将票分成2个档位,每个档位的票数都为 m,游戏运营了 n天,设置一个抢票参数 t。
抢票玩家的游戏登陆天数为 x,若 x≤t,则优先分配第1档位的票,若第1档位已经没有票了,则分配第 2档位的票,若第2档位也没有票,则此玩家没有抢到票;若 x>t,则玩家只能分配第2档位的票,若第2 档位没有票,则此玩家没有抢到票。
米小游是全勤玩家,登陆天数为 n。现在有q个玩家在和米小游抢票,第i个玩家的登陆天数为di。抢票的先后顺序可以看成是一个长度为q+1的排列,但具体的排列未知。
米小游想知道有多少种排列可以使得她至少抢到一张票。
第一行输入四个整数:
n,m,q,t(1≤n,m,q≤103,1≤t≤n):表示游戏运营天数、每个档位的票数、抢票玩家数、抢票参数。
第二行输入q整数 di(1≤di≤n):表示玩家的游戏登陆天数。
输出一个整数,表示答案。由于这个数字可能很大,因此需要输出这个数字对109+7取模后的结果。
输入
2 1 2 2
1 2
输出
4