题目描述

你有四个正整数 $n,a,b,c$，准备用它们玩一个减法游戏。

每一轮操作中，你可以选择将当前数值减去 $a$，或者减去 $b$。游戏持续进行多轮，直到当前数值不超过 $c$ 时停止。

请计算从开始到游戏结束，所有不同的操作序列有多少种。两个操作序列不同，当且仅当总轮数不同，或者在某一轮中一个选择了减 $a$ 而另一个选择了减 $b$。特别地，即使 $a=b$，选择减 $a$ 和选择减 $b$ 也视为两种不同的操作。

由于答案可能很大，请输出答案对 $10^9+7$ 取模的结果。

输入格式

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

输出格式

输出一行一个整数，表示不同的操作序列数对 $10^9+7$ 取模的结果。

样例

1 1 1 1

1

114 51 4 1

176

114514 191 9 810

384178446

提示

• 对 $20\%$ 的数据，$a=b=c=1$，$n \le 30$。
• 对 $40\%$ 的数据，$c=1$，$n \le 10^3$。
• 对全部数据，保证 $1 \le a,b,c \le n \le 2 \times 10^5$。