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