说明

时间限制：1 Sec 内存限制：256 MB 输入文件：ap.in 输出文件：ap.out

求满足以下所有条件的长度为 $ N $ 的整数序列 $ A_1, A_2, ..., A_N $ 的个数，结果对 $ 10^9 + 7 $ 取余后输出。

条件：

1. 序列非严格递增：$ 1 \le A_1 \le A_2 \le \dots \le A_N \le M $；

2. 相邻元素的差值在指定范围内：对所有满足 $ 1 \le i \le N-1 $ 的整数 $ i $，都有 $ D_1 \le A_{i+1} - A_i \le D_2 $。

注：两个序列 $ A' $ 和 $ A'' $ 被视为不同序列，当且仅当存在某个 $ i $ 使得 $ A'_i \neq A''_i $。

输入格式

一行，四个整数 $N,M,D_1,D_2$。

输出格式

输出满足条件的整数序列的个数，结果对 $ 10^9 + 7 $ 取余。

样例

样例 1

3 5 1 2

8

样例说明：

满足条件的序列共 $8$ 个，分别为：( (1,2,3), (1,2,4), (1,3,4), (1,3,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5) )。

样例 2

3 5 2 2

1

样例说明：

仅序列 $(3,5,7)$ 不满足 $A_N \le 5$，实际满足条件的序列为 $(1,3,5)$，故输出 $1$。

样例 3

5 2 1 1

0

样例说明：

序列长度为 $5$，相邻差值固定为 $1$，最小序列为 $(1,2,3,4,5)$，超出 $M=2$，故无满足条件的序列。

样例 4

3141 592653 58 97

200759484

数据范围

对于 4% 的数据，$N \le 5$；

对于 12% 的数据，$N \le 500$；

对于 32% 的数据，$N \le 5000$；

另有 4% 的数据，$M \le 5$；

另有 20% 的数据，$D_1=D_2$；

对于 100% 的数据：$ 2 \le N \le 3 \times 10^5 $，$ 1 \le M \le 10^6 $，$ 0 \le D_1 \le D_2 \le M $。