Fabricating Sculptures

Time limit0.3sMemory limit512 MB

Summary

Count the arrangements of S stacks holding B blocks in total, modulo 1e9+7, where no stack is walled in by taller stacks on both sides.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum
Solved: No attempts yet

Problem

Miguel Angelo is a great sculptor, widely recognized for his outdoor sculptures. In his hometown, it is common to find one of his creations in squares and gardens. People love his sculptures for their beauty and because they still look new after decades. The sculptures do not degrade easily, thanks to the material and technique that Miguel and his staff developed over the years. To build a sculpture, he first constructs its base by stacking blocks of waterproof plaster (his secret material), forming several stacks of blocks in a straight line. He always uses identical blocks, and each stack has at least one block. To stabilize the structure, he surrounds it with two large glass panes, one behind the stacks and one in front of them. Then he waits for rain for as long as it takes. If the structure does not accumulate water during this procedure, Miguel is sure that the base can be used to make a long-lasting piece of artwork. Notice that water accumulates on a block if there are obstacles (other blocks) on both its left and right sides.

Input

The input is a single line with two integers S and B (1 <= S <= B <= 5000), the number of stacks and the number of blocks the base must have.

Output

Output a single line with the number of different bases that do not accumulate water and that Miguel can construct, modulo $10^9+7$ .

Examples2

Example 1
Input
```
3 6
```
Expected output
```
8
```
Example 2
Input
```
3 7
```
Expected output
```
12
```