14949번 - 외계 미생물

항상 B, C가 가득 찬 성적표를 보고 자신이 컴퓨터 공학에 크게 재능이 없다고 생각한 윤영이는 결국 전공을 바꾸어 항공우주학과와 생물학과를 복수전공 하였고, 외계 생물 연구가로 큰 성공을 거두었다.

그러던 중 어떤 행성에서 특이한 외계 미생물을 발견하게 되었고, 이를 신기하게 생각했던 윤영이는 몇 마리를 자신의 연구소로 가지고 왔다. 연구 결과 미생물은 다음과 같은 특징을 가지고 있음을 확인할 수 있었다.

1. 미생물은 스스로 자식을 낳으며, 하루동안 모든 자식을 낳고 죽는다. 낳을 수 있는 자식의 수는 미생물이 자유롭게 정할 수 있다. 또한, 자식은 낳은 순서에 따라 구분된다. 자식은 태어난 다음날부터 새로운 자식을 낳을 수 있다.
2. 미생물은 자식 간의 지나친 경쟁이 생기는 것을 원하지 않는다. 그래서 현재 존재하는 미생물들이 낳은 자식의 수의 총 합이 일정 수 W이하가 되도록 서로 협력한다. (W는 세대가 변해도 일정하다고 가정한다.)
3. 각 미생물은 자식을 안 낳을 수도 있지만, 종족 유지를 위해 모든 미생물이 자식을 낳지 않는 경우는 생기지 않게 한다. (단, 자식을 낳지 않더라도 자신이 태어난 다음날 죽는다.)

윤영이는 이 생물이 번식하는 양상을 재미있어 했고, 미생물 한 마리만 자신의 실험실에 가지고 와서 용기에 담아뒀다. 미생물은 자신이 존재하는 용기에서 (2)번 조건에서 말한 지나친 경쟁이 발생하지 않을 수 있는 최대 자식의 수의 합은 W라고 생각했고, 번식을 시작했다. H일 동안 생길 수 있는 번식 양상의 경우의 수를 구하시오.

첫째 줄에 H와 W가 주어진다. 0 ≤ H ≤ 5, 1 ≤ W ≤ 200 이다.

생물이 H일이 지나는 동안 번식 할 수 있는 양상의 개수를 출력하시오. 경우의 수가 너무 커질 수 있기 때문에 1,000,000,007로 나눈 나머지를 출력하라. 계산 과정에서 32비트 정수 변수가 표현할 수 있는 범위를 넘어서 64비트 정수 변수 (long long)를 사용해야 할 수도 있음에 주의하라.

예제 입력2 의 경우에는 아래와 같은 예시가 있다.