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