P14112

游戏

难度 4 级 小学 动态规划入门 线性DP 加法原理
讨论 统计 74通过 154提交 48.1%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

你有四个正整数 n,a,b,c,并准备用它们玩一个简单的小游戏。

在一轮游戏操作中,你可以选择将 n 减去 a,或是将 n 减去 b。游戏将会进行多轮操作,直到当 n \leq c 时游戏结束。

你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某一轮游戏操作中,一种操作序列选择将 n 减去 a,而另一种操作序列选择将 n 减去 b。如果 a=b,也认为将 n 减去 a 与将 n 减去 b 是不同的操作。

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

输入

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

输出

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

样例

样例 1
输入
1 1 1 1
输出
1
样例 2
输入
114 51 4 1
输出
176
样例 3
输入
114514 191 9 810
输出
384178446

提示

  • 对全部的测试数据,保证 1 \leq a,b,c \leq n \leq 2 \times 10^5。
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交