Line

时间限制:40s      空间限制:128MB

题目描述

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。


题目来源

zcwwzdjn提供

Menuappsclose