题目描述

小明在玩一个闯关游戏，初始分数为 $n$ 分。每天他可以通过两种方式改变分数：

1. 完成挑战任务，减少 $a$ 分
2. 使用特殊道具，减少 $b$ 分

当小明的分数 达到 $c$ 分或以下 时（负数也可以），他就成功通关，游戏结束。小明想知道，从开始到通关，总共有多少种不同的每日操作组合？注意：

• 即使 $a = b$，选择挑战任务和使用道具也算不同的选择
• 计划的不同取决于操作的天数不同，或者在某一日选择了不同的操作类型

由于可能的组合数太大，请输出结果对 $1,000,000,007$ 取模的值。

输入格式

输入一行四个正整数 $n, a, b, c$，分别表示：

• 初始分数 $n$ 分
• 挑战任务得分 $a$ 分
• 道具扣分 $b$ 分
• 目标分数 $c$ 分

输出格式

输出一个整数，表示不同的操作组合数 对 $1,000,000,007$ 取模的结果。

1 1 1 1

1

114 51 4 1

176

114514 191 9 810

384178446

数据范围

• 对于20%的数据：$a=b=c=1，n≤30$
• 对于40%的数据：$c=1，n≤10^3$
• 对于100%的数据：$1≤n≤2×10^5$