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

Бутерброды на завтрак

Бутерброды на завтрак

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

Как только мы приехали готовить лагерь "Берендеевы поляны" к проведению июльской смены ЛКШ, я сразу же пошла в столовую. Дело было не в том, что после долгой дороги мне хотелось есть. Я должна была решить куда более важный вопрос - убедиться в том, что пища, которой будут кормить школьников, будет вкусной и здоровой.

Сотрудники столовой рассказали мне, что умеют готовить целых k разных видов бутербродов и планируют давать их на завтрак в течение всех n дней смены. Лично я больше всего люблю бутерброды с колбасой и плавленым сыром, но понимаю, что рацион должен быть разнообразным. Поэтому я потребовала, чтобы на завтрак не давали одни и те же надоевшие одинаковые бутерброды два дня подряд. Чтобы развлечь себя во время экскурсии по кухне, я посчитала в уме количество способов, которыми столовая сможет составить меню завтраков на эту смену. А вы сможете посчитать это число?

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

В первой строке через пробел записаны целые числа n и k (2n, k100) - продолжительность смены и количество видов бутербродов, которые умеют готовить в столовой.

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

Выведите единственное число - количество способов составить меню завтраков. Это число может быть очень большим, поэтому выведите остаток от деления этого числа на 10007.

Пример

Входные данные #1
3 3
Выходные данные #1
12