Waterloo 2017 Fall D - Drama

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type
2017 Fall Waterloo Local ACM Contest, Problem D

Vera has a grid with H rows and N columns. Rows are numbered 1 to H and columns are numbered 1 to N. Let the cell in the r-th row and c-th column be (r, c). Cells are coloured white or black. A colouring is a pyramid if:

  • Exactly N cells are black.
  • (1, 1) is black.
  • If (r, a) and (r, b) are black, then (r, k) is black for a < k < b.
  • If (r, c) is black, then (r-1, c), if it exists, is black.
  • If (r, c) is black and there is no k < c such that (r, k) is black, then (r+1, c), if it exists, is white.

Two pyramids are different if there is a cell that is white in one pyramid and black in the other. Compute the number of different pyramids modulo 10^9 + 7.

Input

Line 1 contains integers H and N (1 \le H, N \le 10^5).

Output

Print one line with one integer, the number of different pyramids modulo 10^9 + 7.

Sample Input 1

2 6

Sample Output 1

7

Sample Input 2

3 20

Sample Output 2

487

Note

For the first example, the seven pyramids are:

######
......
####..
.##...
####..
..##..
#####.
.#....
#####.
..#...
#####.
...#..
#####.
....#.

Comments

There are no comments at the moment.