Знания --- сила

시간 제한2초메모리 제한1024 MB

요약

처음에 1단계 운반체가 n개 있고, 매일 i단계 운반체가 i개의 새 1단계 운반체를 만들며 단계가 오릅니다. k일 뒤 전체 운반체 수를 10^9+7로 나눈 나머지를 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 시뮬레이션, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

Доктор Стрэндж активно изучает магию. Сегодня он наконец осознал, как распространяются темные силы. Оказывается, они распространяются с помощью так называемых <<носителей силы>>, носителями могут быть кто угодно --- люди, предметы, растения. А также каждый характеризуется своим <<уровнем>> --- количеством новых носителей, которых он может породить. Распространение происходит по следующему незамысловатому закону:

Изначально имеется $n$ носителей, все имеют уровень $1$ .
Каждый следующий день носитель уровня $i$ порождает новые $i$ носителей первого уровня, которые становятся активны только на следующий день.
Сам же носитель переходит на новый уровень $i + 1$ (это означает, что на следующий день он породит уже $i + 1$ новых носителей) и его деятельность на текущий день прекращается.

Всего в распоряжении Стрэнджа имеется $k$ дней. Его интересует, сколько всего носителей появится за это время. За помощью он обратился именно к вам.

입력

В единственной строке входного файла содержится два натуральных числа $n$ и $k$ --- количество носителей изначально и дней соответственно ( $1 \le n \le 1000, 1 \le k \le 10^5$ ).

출력

Выведите одно число --- ответ на задачу. Так как ответ может получится слишком большим, выведите его по модулю $10^9 + 7$ .

힌트

В таблице приведены данные по носителям в конце каждого дня:

день	первый уровень	второй уровень	третий уровень	всего носителей
$0$	$3$	$0$	$0$	$3$
$1$	$3$	$3$	$0$	$2 \times 3$
$2$	$2 \times 3 + 3$	$3$	$3$	$5 \times 3$

예제1

예제 1
입력
```
3 2
```
예상 출력
```
15
```