Множини

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

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

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

Потрібно знайти значення функції $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$ елементу $(\{1\})$ та $k=1$, тому $f(\{1\},1)$=2 $(\{1\}$ та $\{\varnothing \})$.

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

Оцінювання

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

1. ($5$ балів): $k=1$;

2. ($5$ балів): $n\le 10$, $k\le 2$;

3. ($10$ балів): $n\le 15$, $k\le 3$;

4. ($80$ балів): без додаткових обмежень.