Множини
ліміт часу на тест
2 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

Дано числа $$$n$$$ та $$$k$$$.

Нехай $$$[n]$$$ — це множина всіх чисел від $$$1$$$ до $$$n$$$.

Множина $$$A$$$ є підмножиною $$$B$$$, якщо для кожного $$$a\in A$$$, $$$a$$$ також належить $$$B$$$. Пуста множина ($$$\emptyset$$$) є підмножиною будь-якої множини.

Потрібно знайти значення функції $$$f([n],k)$$$.

$$$f([n],1)$$$ повертає кількість підмножин у множині $$$[n]$$$.

$$$f([n],k)$$$ де $$$k>1$$$ повертає суму $$$f(s,k-1)$$$ де $$$s$$$ це підмножина $$$[n]$$$.

Вхідні дані

Перший рядок містить два цілих числа $$$(1\le n,k \le 10^9)$$$.

Вихідні дані

Потрібно вивести $$$f([n],k)$$$. Так як відповідь може бути занадто велика, виведіть її по модулю $$$10^9+7$$$.

Система оцінки

У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.

1. ($$$5$$$ балів): $$$k=1$$$;
2. ($$$5$$$ балів): $$$n\le 10$$$, $$$k\le 2$$$;
3. ($$$10$$$ балів): $$$n\le 15$$$, $$$k\le 3$$$;
4. ($$$80$$$ балів): без додаткових обмежень.

Приклади

Вхідні дані

    1 1

Вихідні дані

    2

Вхідні дані

    2 2

Вихідні дані

    9

Вхідні дані

    3 3

Вихідні дані

    64

Пояснення

У першому прикладі множина з $$$1$$$ елементу $$$(\{1\})$$$ та $$$k=1$$$, тому $$$f(\{1\},1)$$$=2 $$$(\{1\}$$$ та $$$\{\emptyset\})$$$.

У другому прикладі множина з $$$2$$$ елементів $$$(\{1,2\})$$$ та $$$k=2$$$. $$$f(\{1,2\},2)=f(\{1,2\},1)+f(\{1\},1)+$$$ $$$+f(\{2\},1)+f(\{\emptyset\},1)=4+2+2+1=9$$$.