iktk   2년 전

문제

당신은 미생물을 연구하는 연구원이다. 어느날, 당신은 엄청난 번식력을 가진 미생물 A를 발견하였다. 당신은 미생물 A의 번식 과정을 관찰하여 다음과 같이 분석하였다.

  • $0$일째에는 미생물 A $n$마리가 있다. 이 미생물들의 나이는 $1$살이다.
  • 하루가 지날 때마다, 전날 있었던 미생물 A들은 세포 분열을 통해 나이가 $1$살인 미생물 A을 자기 나이만큼 생성하고, 나이를 한 살 더 먹는다.(이 과정을 번식이라 한다) 예를 들어, 나이가 $i$살인 미생물 A는 하루가 지나면 $1$살인 미생물 A $i$마리를 생성하고, $i+1$살이 된다. (따라서 그 다음 날에는 $i+1$마리를 생성할 것이다.)
  • 방금 생성된 미생물 A는 생성된 다음 날부터 번식을 시작한다.

관찰 $k$일째에 몇 마리의 미생물 A가 있을지를 계산해 보자.

입력

문제에 언급된 두 정수 $n$과 $k$가 주어진다. ($1\le n\le 1000$, $1\le k\le 10^5$)

출력

문제의 정답을 $10^9 + 7$로 나눈 나머지를 출력한다.

노트

예제 설명:

날짜 나이가 $1$살인 미생물 A 나이가 $2$살인 미생물 A 나이가 $3$살인 미생물 A 미생물 A의 총 마리수
$0$ $3$ $0$ $0$ $3$
$1$ $3$ $3$ $0$ $2 \times 3$
$2$ $2 \times 3 + 3$ $3$ $3$ $5 \times 3$

댓글을 작성하려면 로그인해야 합니다.