당신은 미생물을 연구하는 연구원이다. 어느날, 당신은 엄청난 번식력을 가진 미생물 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$)
iktk 2년 전 4
문제
당신은 미생물을 연구하는 연구원이다. 어느날, 당신은 엄청난 번식력을 가진 미생물 A를 발견하였다. 당신은 미생물 A의 번식 과정을 관찰하여 다음과 같이 분석하였다.
관찰 $k$일째에 몇 마리의 미생물 A가 있을지를 계산해 보자.
입력
문제에 언급된 두 정수 $n$과 $k$가 주어진다. ($1\le n\le 1000$, $1\le k\le 10^5$)
출력
문제의 정답을 $10^9 + 7$로 나눈 나머지를 출력한다.
노트
예제 설명: