题目描述

西华旅行社为了高效运作，准备从$n$名报名者中招募一批导游，要求恰好招募$k$人。其中有$m$人有“外语专业证书”(可带领海外游客)，另有$n-m$人不具备此能力。由于接待国际旅行团的需求，公司要求至少从拥有外语专业证书的$m$人中选拔出$x$人(或更多)，以确保整个团队在出行时能够覆盖境外游客的需求。

请你帮忙计算： 从$n$位报名者中选出恰好$k$人，且其中恰好$x$人具有外语专业证书，每位报名者至多被选一次，一共有多少种不同的选拔方案？结果可能非常庞大，你只要输出该方案对$10^9 + 7$取模(记作$mod 10^9 + 7$)后的结果。

输入

一行包含四个整数$n$，$m$，$k$，$x$，分别表示报名者总人数，拥有外语专业证书的人数，需要选出的总人数，至少要有多少拥有外语专业证书的人数。

$1\le n \le 2*10^6$

$1 \le m \le 2*10^6$

$1 \le k \le 2*10^6$

$1\le x \le 2*10^6$

输出

一行输出满足条件的选拔方案数，取模$10^9 + 7$之后的结果。

样例

输入

5 2 3 1

输出

9