E - Popping Balls Editorial /

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 like rrbbb.
  • You remove 4th ball (b) and give it to Snuke. Now the row looks like rrbb.
  • You remove 1st ball (r) and give it to Snuke. Now the row looks like rbb.
  • You remove 3rd ball (b) and give it to Snuke. Now the row looks like rb.
  • You remove 1st ball (r) and give it to Snuke. Now the row looks like b.
  • 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