题目描述

有 $n_1$ 个相同的红球和 $n_2$ 个相同的蓝球。

要求将这些球从左到右排列起来。

同时要求排列中不能存在大于 $k_1$ 个连续的红球，且不能存在大于 $k_2$ 个连续的蓝球。

问：有多少种合法的排列方案？

由于合法的排列方案数可能很多，所以你只需要输出合法的排列方案数模 $10^9 + 7$ 的结果即可。

注：两种排列方案被视为不同，当且仅当这两个排列至少存在一个位置放置的球的颜色不一样。

输入格式

一行，四个整数 $n_1, n_2, k_1, k_2$，以空格分隔。

输出格式

输出一个整数，表示合法的排列方案数模 $10^9 + 7$ 的结果。

2 1 1 10

1

2 3 1 2

5

2 4 1 1

0

1000 1000 10 11

884764969

说明/提示

样例解释

我们用 R 表示一个红球，用 B 表示一个蓝球。

样例1：只存在一种合法的排列方案：RBR。

样例2：存在 $5$ 种合法的排列方案：RBRBB、RBBRB、BRBRB、BRBBR、BBRBR。

样例3：不存在合法的排列方案。

数据规模与约定

• 对于 $30\%$ 的数据，$n_1, n_2 \le 10; k_1, k_2 \le 10$
• 对于 $60\%$ 的数据，$n_1, n_2 \le 100; k_1, k_2 \le 10$
• 对于 $100\%$ 的数据，$1 \le n_1, n_2 \le 1000; 1 \le k_1, k_2 \le 100$