Множини#253
Дано числа та .
Нехай — це множина всіх чисел від до .
Множина є підмножиною , якщо для кожного a\in A, також належить . Пуста множина () є підмножиною будь-якої множини.
Потрібно знайти значення функції f([n],k).
f([n],1) повертає кількість підмножин у множині .
f([n],k) де k>1 повертає суму f(s,k-1) де це підмножина .
Перший рядок містить два цілих числа (1\le n,k \le 10^9).
Потрібно вивести f([n],k). Так як відповідь може бути занадто велика, виведіть її по модулю 10^9+7.
Приклад
Приклад 1
Приклад 2
У першому прикладі множина з елементу та k=1, тому f(\{1\},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.
У цій задачі існують умовні блоки. Якщо ваше рішення буде працювати правильно для певних обмежень, то воно отримуватиме певну кількість балів. Зверніть увагу, що оцінювання й досі потестове.
( балів): k=1;
( балів): n\le 10, k\le 2;
( балів): n\le 15, k\le 3;
( балів): без додаткових обмежень.