题目描述

观察这个数列：

1 3 0 2 −1 1 −2 ⋯

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

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

输入描述

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

其中，1≤n≤1000，−10⁹≤s≤10⁹，1≤a,b≤10⁶。

输出描述

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

输入输出样例

示例

输入

4 10 2 3

输出

2

样例说明

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