http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1503. Line(王迪)
时间限制:5.0s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  Wayne喜欢排队……不对,是Wayne所在学校的校长喜欢看大家排队,尤其是在操场上站方阵。
  某日课间操时,校长童心大发想了一个极具观赏性的列队方案,如下:
  1. 方阵排成N行,每行恰好M个学生。
  2. 由于校长喜欢女孩子,所以在一行上不能有连续P个男生。
  3. 由于校长喜欢女孩子,所以在校长看来,一列全是男生是不好的,全男生的列数不能超过Q。
  Wayne因为感冒了所以不用参加列队,不过他看着大家排队排得不亦乐乎,于是他想知道,在男女生数目无限制的情况下,有多少种列队方案?
  两种方案被视作不同,表明存在至少一个二元组(i,j)而两种方案中第i行第j列的同学性别不同。另外,因为答案可能很大,所以请把答案模10^9 + 7。
输入格式
  输入仅一行4个正整数,依次是N,M,P,Q。
输出格式
  输出仅一行,表示答案。
样例输入
2 3 3 1
样例输出
46
数据规模和约定
  对于5%的数据,满足P = 1。
  对于另外10%的数据,满足N * M <= 20。
  对于另外15%的数据,满足N <= 2,M <= 10^6。
  对于另外10%的数据,满足N <= 2。
  对于另外20%的数据,满足N <= 4,P <= 2,Q <= 2。
  对于100%的数据,满足1 <= N <= 8,1 <= M <= 10^18,1 <= P <= 3,0 <= Q <= 3。