블록 쌓기

1×1×w 받침 블록 위에 1×1×1, 1×1×2, 1×1×3 블록을 무한히 쌓아 높이가 h 이하인 구조의 수를 센다. 긴 블록은 양 끝이 다른 블록에 받쳐져야 한다.

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

문제

영선이는 크기가 1×1×11 \times 1 \times 1, 1×1×21 \times 1 \times 2, 1×1×31 \times 1 \times 3인 블록을 원하는 만큼 쓸 수 있다. 여기에 크기가 1×1×w1 \times 1 \times w인 블록이 하나 더 있고, 이 블록을 기초 블록이라고 한다.

영선이는 기초 블록 하나와 나머지 블록으로 구조를 만든다. 모든 블록은 기초 블록과 연결되어 있어야 하고, 정수가 아닌 위치에는 블록을 놓을 수 없다. 긴 블록(1×1×21 \times 1 \times 2, 1×1×31 \times 1 \times 3)은 양 끝이 모두 다른 블록 위에 놓여야 한다. 1×1×31 \times 1 \times 3 블록은 가운데 칸 아래가 비어 있어도 된다.

왼쪽 그림은 올바른 구조이고, 오른쪽 그림은 만들 수 없는 구조이다.

구조의 높이는 기초 블록 위에 쌓은 층의 개수이다. 블록을 하나도 쌓지 않은 구조의 높이는 00이고, 이 구조도 한 가지로 센다.

기초 블록의 길이 ww와 높이 제한 hh가 주어졌을 때, 기초 블록 하나와 개수가 무한한 블록으로 만들 수 있는 구조 중에서 높이가 hh를 넘지 않는 것이 몇 가지인지 구하는 프로그램을 작성하시오.

아래 그림은 w=3w = 3, h=2h = 2인 경우의 84가지 구조를 모두 그린 것이다.

입력

첫째 줄에 wwhh가 공백으로 구분되어 주어진다. (1w,h101 \le w, h \le 10)

출력

첫째 줄에 구조의 개수를 10000000071000000007로 나눈 나머지를 출력한다.