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

문제

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

Изначально имеется $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$