题目描述

观察这个数列：

$1,3,0,2,-1,1,-2, \cdots$。

这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。

栋栋对这种数列很好奇，他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢？

输入格式

输入的第一行包含四个整数 $n,s,a,b$，含义如前面说述。

输出格式

输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以 $100000007$ 的余数。

4 10 2 3

2

提示

【样例说明】

这两个数列分别是 2 4 1 3 和 7 4 1 -2。

【数据规模与约定】

对于 $10\%$ 的数据，$1 \le n \le 5$，$0 \le s \le 5$，$1 \le a,b \le 5$；

对于 $30\%$ 的数据，$1 \le n \le 30$，$0 \le s \le 30$，$1 \le a,b \le 30$；

对于 $50\%$ 的数据，$1 \le n \le 50$，$0 \le s \le 50$，$1 \le a,b \le 50$；

对于 $70\%$ 的数据，$1 \le n \le 100$，$0 \le s \le 500$，$1 \le a,b \le 50$；

对于 $100\%$ 的数据，$1 \le n \le 1000$，$-10^9 \le s \le 10^9$，$1 \le a,b \le 10^6$。

时限 1 秒, 256M。蓝桥杯 2014 年第五届省赛