题目描述

FJ 农场的射电望远镜收到了来自外太空的神秘信号，奶牛贝蒂将其解码后得到如一个数列：

\(1\) \(3\) \(0\) \(2\) \(-1\) \(1\) \(-2\) \(...\)

贝蒂发现这个数列是有规律的，数列中后一项总是比前一项增加 \(2\) 或者减少 \(3\)，贝蒂将这种后一项总是比前一项增加 \(a\) 或者减少 \(b\) 的数列命名为 \(BD\) 数列。

贝蒂想知道对于一个给定长度为 \(n\)，数列总和为 \(s\)，并且后一项总是比前一项增加 \(a\) 或者减少 \(b\) 的 \(BD\) 数列有多少种。

格式

输入格式

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

输出格式

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

样例1

输入样例1

4 10 2 3

输出样例1

2

样例2

输入样例2

15 38 3 1

输出样例2

1091

样例1解释

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

限制

对于 \(100\%\) 的数据，\(1≤n≤1000，-1,000,000,000≤s≤1,000,000,000，1≤a,b≤1,000,000\)。

来源

地址：\(\text{Online~Judge}\)
作者：\(hoogy\)
模拟赛\(T4\)