Popping Balls

AtCoder

IDcode_festival_2017_qualb_e

Time2000ms

Memory256MB

Difficulty—

$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$ [samples]

Samples

Input #1

3 3

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

This way, Snuke receives balls in the order `rbrbrb`.

Input #2

4 4

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.

Input #3

7 9

Output #3

Input #4

1987 1789

Output #4

456315553

API Response (JSON)

{
  "problem": {
    "name": "Popping Balls",
    "description": {
      "content": "$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, ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "code_festival_2017_qualb_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$A + B$ balls are arranged in a row. The leftmost $A$ balls are colored red, and the rightmost $B$ balls are colored blue.\nYou perform the following operation:\n\n*   First, you choose two integers $s, ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments