Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1600 点
問題文
A + B 個のボールが一列に並べられています。 左から A 個のボールは赤で、右から B 個のボールは青で塗られています。
あなたは、以下の操作を行います:
- 最初に、 1 \leq s, t \leq A + B を満たす整数 s, t を選びます。
- 次に、以下のステップを A + B 回繰り返します: 各ステップでは、あなたは左から 1 番目または s 番目 (存在すれば) または t 番目 (存在すれば、すべて 1-based) のボールを選び、すぬけ君にあげます。
すぬけ君に何通りの方法でボールをあげることができるでしょうか? Mod 10^9 + 7 で求めてください。
ここで、ある整数 k に対し、 k 番目にすぬけ君にあげるボールの色が異なるとき、二つの方法は異なるとみなします。 特に、 s, t の選択は関係ありません。 また、同じ色の二つのボールは区別しません。
制約
- 1 \leq A, B \leq 2000
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
3 3
出力例 1
20
3 個の赤いボールと 3 個の青いボールをあげる方法は 20 通りあります。 それらのすべての方法が可能であることが分かります。
以下は操作の例です (r
は赤を、 b
は青をあらわします):
- s = 3, t = 4 を選ぶ。
- 最初、列は
rrrbbb
となっています。 - 3 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はrrbbb
となっています。 - 4 番目のボール (
b
) を取り除きすぬけ君にあげます。 列はrrbb
となっています。 - 1 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はrbb
となっています。 - 3 番目のボール (
b
) を取り除きすぬけ君にあげます。 列はrb
となっています。 - 1 番目のボール (
r
) を取り除きすぬけ君にあげます。 列はb
となっています。 - 1 番目のボール (
b
) を取り除きすぬけ君にあげます。 列は空になります。
この方法では、すぬけ君は rbrbrb
の順でボールを受け取ります。
入力例 2
4 4
出力例 2
67
4 個の赤いボールと 4 個の青いボールをあげる方法は 70 通りあります。
そのうち、 bbrrbrbr
, brbrbrbr
, brrbbrbr
だけが不可能です。
入力例 3
7 9
出力例 3
7772
入力例 4
1987 1789
出力例 4
456315553
Score : 1600 points
Problem Statement
A + B balls are arranged in a row. The leftmost A balls are colored red, and the rightmost B balls are colored blue.
You perform the following operation:
- First, you choose two integers s, t such that 1 \leq s, t \leq A + B.
- Then, you repeat the following step A + B times: In each step, you remove the first ball or the s-th ball (if it exists) or the t-th ball (if it exists, all indices are 1-based) from left in the row, and give it to Snuke.
In how many ways can you give the balls to Snuke? Compute the answer modulo 10^9 + 7.
Here, we consider two ways to be different if for some k, the k-th ball given to Snuke has different colors. In particular, the choice of s, t doesn't matter. Also, we don't distinguish two balls of the same color.
Constraints
- 1 \leq A, B \leq 2000
Input
Input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
3 3
Sample Output 1
20
There are 20 ways to give 3 red balls and 3 blue balls. It turns out that all of them are possible.
Here is an example of the operation (r
stands for red, b
stands for blue):
- You choose s = 3, t = 4.
- Initially, the row looks like
rrrbbb
. - You remove 3rd ball (
r
) and give it to Snuke. Now the row looks likerrbbb
. - You remove 4th ball (
b
) and give it to Snuke. Now the row looks likerrbb
. - You remove 1st ball (
r
) and give it to Snuke. Now the row looks likerbb
. - You remove 3rd ball (
b
) and give it to Snuke. Now the row looks likerb
. - You remove 1st ball (
r
) and give it to Snuke. Now the row looks likeb
. - You remove 1st ball (
b
) and give it to Snuke. Now the row is empty.
This way, Snuke receives balls in the order rbrbrb
.
Sample Input 2
4 4
Sample Output 2
67
There are 70 ways to give 4 red balls and 4 blue balls.
Among them, only bbrrbrbr
, brbrbrbr
, and brrbbrbr
are impossible.
Sample Input 3
7 9
Sample Output 3
7772
Sample Input 4
1987 1789
Sample Output 4
456315553