Розподіл множини#6745
Руслан має друзів, і всі вони святкують день народження завтра. Вчора він придбав різних фотоальбомів і планує подарувати їх своїм друзям. Звісно, кожен має отримати принаймні один фотоальбом. Ваше завдання — визначити, скількома способами це можна зробити.
Усі фотоальбоми є унікальними. Два розподіли вважаються однаковими, якщо вони відрізняються лише порядком альбомів у подарунках або особами, які їх отримують.
У єдиному рядку вхідних даних подано два числа, розділені пробілом: 1 \leq N \leq 1000000000, 1 \leq K \leq \min(N, 10).
Вихідні дані повинні містити одне число — кількість можливих способів розподілити альбоми за модулем .
Приклад 1