Description
你有四个正整数n, a, b, c ,并准备它们玩个简单的游戏。
在一轮游戏操作中,你可以选择将n减去a,或是将n减去b。游戏将会进多轮操作,直到当n<=c时游戏结束。
你想知道游戏结束时有多少种不同的游戏操作序列。两种游戏操作序列不同,当且仅当游戏操作轮数不同,或是某 轮游戏操作中,种操作序列选择将n减去a,另种操作序列选择将n减去b。如果a=b ,也认为将 减去a与将n减去b是不同的操作。
由于答案可能很大,你只需要求出答案对1 000 000 007取模的结果。
Input
一行四个正整数n, a, b, c。保证 1<=a, b, c <=n。
Output
一行一个整数,表不同的游戏操作序列数量对1 000 000 007 取模的结果。
HINT
对于20%的测试点,保证 a=b=c=1,n<=30 。
对于40的测试点,保证c=1, n<=103。
对于所有测试点,保证 1<=n<=2*105。