eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Set Division

Set Division

Лимит времени 0.25 секунд
Лимит использования памяти 256 MiB

Ruslan has K friends. And all of them have birthday tomorrow. He has bought N different photo albums yesterday, and wants to present these photo albums to his friends. Of course, he can't give less than 1 photo album to anybody. Your task is to calculate how many possible ways is there to do it.

All photo albums are different. Two distributions are considered the same if they differ only by order of albums in the gifts or by the persons receiving gifts.

Входные данные

In the only line of the input there are two numbers separated by a space — 1N1000000000, 1Kmin(N, 10).

Выходные данные

Output should contain one number — the number of possible ways to distribute the albums modulo 2007.

Пример

Входные данные #1
3 2
Выходные данные #1
3
Источник Izhevsk STU Contest, Petrozavodsk training camp, February 6, 2009