| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 41 | 22 | 19 | 50.000% |
Доктор Стрэндж активно изучает магию. Сегодня он наконец осознал, как распространяются темные силы. Оказывается, они распространяются с помощью так называемых <<носителей силы>>, носителями могут быть кто угодно --- люди, предметы, растения. А также каждый характеризуется своим <<уровнем>> --- количеством новых носителей, которых он может породить. Распространение происходит по следующему незамысловатому закону:
Всего в распоряжении Стрэнджа имеется $k$ дней. Его интересует, сколько всего носителей появится за это время. За помощью он обратился именно к вам.
В единственной строке входного файла содержится два натуральных числа $n$ и $k$ --- количество носителей изначально и дней соответственно (1ドル \le n \le 1000, 1 \le k \le 10^5$).
Выведите одно число --- ответ на задачу. Так как ответ может получится слишком большим, выведите его по модулю 10ドル^9 + 7$.
3 2
15
В таблице приведены данные по носителям в конце каждого дня:
| день | первый уровень | второй уровень | третий уровень | всего носителей |
|---|---|---|---|---|
| 0ドル$ | 3ドル$ | 0ドル$ | 0ドル$ | 3ドル$ |
| 1ドル$ | 3ドル$ | 3ドル$ | 0ドル$ | 2ドル \times 3$ |
| 2ドル$ | 2ドル \times 3 + 3$ | 3ドル$ | 3ドル$ | 5ドル \times 3$ |