题目描述

小U有一个正整数 $n$，他有两个神奇的转换器：转换器A每次可以将数字减少 $a$，转换器B每次可以将数字减少 $b$。

小U会重复使用这些转换器，直到数字变得足够小（$\leq c$）为止。在整个过程中，他会记录下每次使用的是哪个转换器，形成一个操作序列。

例如：如果 $n=5, a=2, b=3, c=1$，一种可能的操作序列是：先用A(5→3)，再用A(3→1)，最后得到1≤c，序列为"AA"。

现在小U想知道，一共有多少种不同的操作序列？两种序列不同，只要它们在某一步使用的转换器不同（即使 $a=b$，也认为转换器A和B是不同的操作）。

由于答案可能非常大，你只需要输出答案对 $10^9+7$ 取模的结果。

输入格式

一行四个整数 $n,a,b,c$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

1 1 1 1

输出 #1

1

输入输出样例 #2

输入 #2

114 51 4 1

输出 #2

176

输入输出样例 #3

输入 #3

114514 191 9 810

输出 #3

384178446

说明/提示

数据规模与约定

• 对 $20\%$ 的数据，$a=b=c=1$，$n \leq 30$。
• 对 $40\%$ 的数据，$c = 1$，$n \leq 10^3$。
• 对全部的测试数据，保证 $1 \leq a,b,c \leq n \leq 2 \times 10^5$。