Бутерброды на завтрак
Как только мы приехали готовить лагерь "Берендеевы поляны" к проведению июльской смены ЛКШ, я сразу же пошла в столовую. Дело было не в том, что после долгой дороги мне хотелось есть. Я должна была решить куда более важный вопрос - убедиться в том, что пища, которой будут кормить школьников, будет вкусной и здоровой.
Сотрудники столовой рассказали мне, что умеют готовить целых k разных видов бутербродов и планируют давать их на завтрак в течение всех n дней смены. Лично я больше всего люблю бутерброды с колбасой и плавленым сыром, но понимаю, что рацион должен быть разнообразным. Поэтому я потребовала, чтобы на завтрак не давали одни и те же надоевшие одинаковые бутерброды два дня подряд. Чтобы развлечь себя во время экскурсии по кухне, я посчитала в уме количество способов, которыми столовая сможет составить меню завтраков на эту смену. А вы сможете посчитать это число?
Входные данные
В первой строке через пробел записаны целые числа n и k (2 ≤ n, k ≤ 100) - продолжительность смены и количество видов бутербродов, которые умеют готовить в столовой.
Выходные данные
Выведите единственное число - количество способов составить меню завтраков. Это число может быть очень большим, поэтому выведите остаток от деления этого числа на 10007.