题目描述

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。