题目描述

勇者决定挑战盘踞在黑森林深处的恶龙。恶龙拥有 $n$ 点生命值，勇者每回合可以选择以下两种攻击方式中的一种：

拔剑斩击:对恶龙造成 $a$ 点伤害。

念咒施法：对恶龙造成 $b$ 点伤害。

战斗会持续进行多个回合，直到恶龙的生命值降至 $c$ 或以下时，恶龙便会投降，战斗立即结束。 小明想知道，从战斗开始到恶龙投降，共有多少种不同的攻击序列。两种攻击序列不同，当且仅当总回合数不同，或是存在某一回合种，一种序列选择拔剑斩击，而另一种序列选择念咒施法。即使 $a=b$，拔剑斩击与念咒施法仍被视为不同的操作。

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

输入格式

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

输出格式

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

1 1 1 1

1

114 51 4 1

176

114514 191 9 810

384178446

提示

样例 1 解释

初始时 $n<=c$，游戏直接结束，无需进行任何操作。唯一的操作序列为“空序列”，答案为 $1$。

数据规模与约定

• 对 $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$。