Бутерброди на сніданок
Як тільки ми приїхали готувати табір "Берендеєві поляни" до проведення липневої зміни ЛКШ, я відразу ж пішла у їдальню. Справа була не у тому, що після довгої дороги мені захотілось їсти. Я повинна була вирішити куди більш важливіше питання - переконатись у тому, що їжа, якою будуть годувати школярів, буде смачною і корисною.
Співробітники їдальні розповіли мені, що вміють готувати цілих k різних видів бутербродів і планують давати їх на сніданок протягом усіх n днів зміни. Особисто я більше усього полюбляю бутерброди з ковбасою та плавленим сиром, але розумію, що раціон повинен бути різноманітним. Тому я поставила вимогу, щоб на сніданок не подавали одні й ті ж надоївші однакові бутерброди два дні підряд. Щоб розважити себе під час екскурсії по кухні, я порахувала подумки кількість способів, якими їдальня зможе скласти меню сніданків на цю зміну. А ви зможете порахувати це число?
Вхідні дані
У першому рядку через пропуск записано цілі числа n та k (2 ≤ n, k ≤ 100) - тривалість зміни та кільеість видів бутербродів, які вміють готувати у їдальні.
Вихідні дані
Виведіть єдине число - кількість способів скласти меню сніданків. Це число може бути дуже великим, тому виведіть залишок від ділення цього числа на 10007.