[蓝桥杯 2014 省 A] 波动数列

题目描述

观察这个数列: $1,3,0,2,-1,1,-2, \cdots $。 这个数列中后一项总是比前一项增加 $2$ 或者减少 $3$。 栋栋对这种数列很好奇,他想知道长度为 $n$ 和为 $s$ 而且后一项总是比前一项增加 $a$ 或者减少 $b$ 的整数数列可能有多少种呢?

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

4 10 2 3

输出样例 #1

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 年第五届省赛