Breakfast Sandwiches
Upon arriving to prepare the "Berendeyevy Polyany" camp for the July session of LKSH, my first stop was the dining hall. It wasn't because I was hungry after the long journey, but because I had a crucial task: ensuring the food served to the students would be both delicious and nutritious.
The dining hall staff informed me that they could prepare a total of k different types of sandwiches, which they planned to serve for breakfast over the course of n days during the session. While I personally favor sandwiches with sausage and melted cheese, I recognize the importance of a varied diet. Therefore, I insisted that the same type of sandwich should not be served for breakfast on consecutive days. As I toured the kitchen, I amused myself by calculating the number of possible ways the dining hall could organize the breakfast menu for the session. Can you determine this number?
Input
The first line contains two integers n and k (2 ≤ n, k ≤ 100) - representing the duration of the session and the number of sandwich types the dining hall can prepare.
Output
Output a single number - the number of ways to arrange the breakfast menu. Since this number can be very large, provide the remainder when this number is divided by 10007.