题目描述

观察这个数列：

1 3 0 2 -1 1 -2 …

这个数列中后一项总是比前一项增加2或者减少3，​且每一项都为整数​。

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

输入格式

共一行，包含四个整数$𝑛,𝑠,𝑎,𝑏$，含义如前面所述。

输出格式

共一行，包含一个整数，表示满足条件的方案数。

由于这个数很大，请输出方案数除以 $100000007$ 的余数。

4 10 2 3

2

样例解释

两个满足条件的数列分别是2 4 1 3和7 4 1 -2。

提示

$1≤𝑛≤1000,$

$−10^9≤𝑠≤10^9,$

$1≤𝑎,𝑏≤10^6$