返回小组 开始 2026-05-01 08:40:00

线性动态规划专项训练

结束 2026-05-01 17:00:00
Contest is over.
当前 2026-05-08 03:03:25

A. 游戏

描述

你有四个正整数 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

输入

114 51 4 1

输出

176

输入

114514 191 9 810

输出

384178446

提示

  • 对全部的测试数据,保证 1 \leq a,b,c \leq n \leq 2 \times 10^5

Submit

登录

注册
时间限制 1 秒
内存限制 128 MB
提交