Розподіл множини

Руслан має K друзів, і всі вони святкують день народження завтра. Вчора він придбав N різних фотоальбомів і планує подарувати їх своїм друзям. Звісно, кожен має отримати принаймні один фотоальбом. Ваше завдання — визначити, скількома способами це можна зробити.

Усі фотоальбоми є унікальними. Два розподіли вважаються однаковими, якщо вони відрізняються лише порядком альбомів у подарунках або особами, які їх отримують.

Вхідні дані

У єдиному рядку вхідних даних подано два числа, розділені пробілом: 1 ≤ N ≤ 1000000000, 1 ≤ K ≤ min(N, 10).

Вихідні дані

Вихідні дані повинні містити одне число — кількість можливих способів розподілити альбоми за модулем 2007.

Приклади