Problem F: 【2018提高】量子计算

做完基因锁手术后，小Ｘ又被机器狗带回到了会客舱，外星首领请小Ｘ喝了杯龙冠龙井，说道：“此茶乃 G20 峰会专用，对你的术后恢复大有裨益，在送你回地球之前，你可以再问一个问题。”小Ｘ问道：“人类这么多年都未能破译基因密码，你们是如何做到的呢？”外星首领答道：“这全靠我们的科学家发明的128 位量子计算机，它的计算速度大约是 2 的 128 次方，而地球上最快的光电计算机目前最快能算到 2 的32 次方左右。”小Ｘ梦醒之后上网查阅了一下有关量子计算机的最新发展状况，发现米国已经在研制 50 位的量子计算机了，联想到最近发生的中兴事件，小Ｘ心想一旦量子计算技术再受制于人，那后果就十分严重了，于是小Ｘ计划研制 64 位的量子计算机，他觉得这个任务有些艰巨，需要找几位天资聪颖且志同道合的小伙伴来帮助自己，于是就想到了这次的程序设计小能手比赛，小Ｘ出了下面这个题目来考考小朋友
们，通过的同学将有机会跟小Ｘ一起研制量子计算机哦！一个圆被均分成了 n 个区域，现有 m 种可供选择的颜色给图中的区域涂色，每一个区域只能涂一种颜色，且相邻的区域要涂不同的颜色，问有多少种不同的涂色方式？由于结果很大，你只要输出结果除以10000007 的余数的值。
以下是 n=5 的时候的圆被分成的样子。

输入数据仅有一行包含两个用空格隔开的正整数 n,m，即圆被分成了 n 个区域，有 m 种可供选择的颜色。

输出数据仅有一行包含一个整数，表示不同的涂色方式，请输出对 10000007 求余后的值。

5 3

30

10%的数据 m=2
40%的数据 m<=3，n<=15
70%的数据 m<=5，n<=100
100%的数据 m<=100，n<=1000