시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 4 4 100.000%

문제

영선이는 크기가 1×1×1, 1×1×2, 1×1×3인 블럭을 가지고 있다. 또, 크기가 1×1×w인 블럭을 가지고 있는데, 이 블럭은 기초 블럭이라고 한다.

영선이는 블럭과 기초 블럭을 이용해서 구조를 만드려고 한다. 모든 블럭은 기초 블럭과 연결되어 있어야 한다. 정수가 아닌 위치에는 블럭을 놓을 수 없다. 긴 블럭 (1×1×2, 1×1×3)의 경우에는 블럭의 양 끝이 다른 블럭의 위에 있어야 한다. 1×1×3 블럭의 경우에 가운데 칸의 아래는 비어 있어도 된다.

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

구조의 높이는 블럭을 쌓은 층의 개수이다. 기초 블럭의 높이 w와 h가 주어졌을 대, 블럭(개수는 무한대)과 기초 블럭 하나를 가지고 만들 수 있는 구조 중, 높이가 h를 넘지 않는 것의 개수를 구하는 프로그램을 작성하시오.

아래 그림은 w = 3, h = 2인 경우 모든 84가지 구조이다.

입력

첫째 줄에 w와 h (1 ≤ w, h ≤ 10)가 주어진다.

출력

첫째 줄에 문제의 정답을 1000000007로 나눈 나머지를 출력한다.

예제 입력 1

1 3

예제 출력 1

4

예제 입력 2

3 1

예제 출력 2

13

예제 입력 3

3 2

예제 출력 3

84

예제 입력 4

4 9

예제 출력 4

132976888

예제 입력 5

5 5

예제 출력 5

11676046

출처