题目描述

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 \times m \le 20$。

对于另外 $15\%$ 的数据，$n \le 2$，$m \le 10^6$。

对于另外 $10\%$ 的数据，$n \le 2$。

对于另外 $20\%$ 的数据，$n\le 4$，$p \le 2$，$q\le 2$。

对于 $100\%$ 的数据，$1 \le n \le 8$，$1 \le m \le 10^{18}$，$1 \le p \le 3$，$0 \le q \le 3$。