选择颜色
题号：NC19115
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

n个人排成一个环形，每个人要从c种颜色中选择一个。
牛牛希望相邻的人选择的颜色是不同的
问有多少种方案。
输出方案数对10007取模的结果。
人是有顺序的，环旋转同构算不同的方案。

输入描述:

输入只有一行，包含用空格分开的两个整数，表示n和c。

输出描述:

输出一行一个整数，表示答案。
示例1

输入

复制 
4 3

输出

复制 
18
示例2

输入

复制 
1000000000 100

输出

复制 
726

说明

对10007取模。

备注:

对于所有数据： 3 <= n <= 1000000000, 3 <= c <= 100
20分： c <= 3
40分： c <= 4
70分： n <= 10000