드라마

H행 N열 격자에 검은 칸이 정확히 N개인 피라미드 색칠의 수를 10^9+7로 나눈 나머지를 구한다.

어려움9조합론동적 계획법수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

베라에게 HHNN열 격자가 있다. 행은 위에서부터 1번부터 HH번까지, 열은 왼쪽에서부터 1번부터 NN번까지 번호를 매긴다. rrcc열에 있는 칸을 (r,c)(r, c)로 쓴다. 각 칸은 흰색 또는 검은색으로 칠해져 있다. 칠한 결과가 다음 조건을 모두 만족하면 피라미드라고 부른다.

  • 검은 칸이 정확히 NN개다.
  • (1,1)(1, 1)은 검은색이다.
  • (r,a)(r, a)(r,b)(r, b)가 모두 검은색이면, a<k<ba < k < b인 모든 kk에 대해 (r,k)(r, k)도 검은색이다.
  • (r,c)(r, c)가 검은색이고 (r1,c)(r - 1, c)가 존재하면, (r1,c)(r - 1, c)도 검은색이다.
  • (r,c)(r, c)가 검은색이고 (r,k)(r, k)가 검은색인 k<ck < c가 하나도 없으면, (r+1,c)(r + 1, c)가 존재하는 경우 그 칸은 흰색이다.

색이 다른 칸이 하나라도 있으면 두 피라미드는 서로 다르다. 서로 다른 피라미드의 개수를 109+710^9 + 7로 나눈 나머지를 구하라.

입력

첫째 줄에 정수 HHNN이 공백을 사이에 두고 주어진다. (1H,N1051 \le H, N \le 10^5)

출력

서로 다른 피라미드의 개수를 109+710^9 + 7로 나눈 나머지를 한 줄에 출력한다.

힌트

H=2H = 2, N=6N = 6일 때 피라미드는 다음 7가지다. #은 검은 칸, .은 흰 칸을 나타낸다.

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