OI题库

描述

今天是情人节，小杉在参加一个valentine’s party!

Oh,it sounds good.

现在已经是晚上10点了，参加party的n个人很无聊，于是开始玩一个游戏。

每个人先穿一件白外套，再站成一个圈，然后给每件外套上色。总共有k种颜色可以上。

一个可爱的上色方案应该满足对于每一个人，他身边的两个人所穿的外套颜色都和他所穿的不同。

小杉现在想知道总共有多少种可爱的上色方案。

输入格式

一行两个整数n,k(1<=n<=3000,1<=k<=10)

输出格式

仅有一行，一个整数，为上色方案数对19900801取模的结果

样例输入

2 2

样例输出

2

样例解释

譬如小杉和小小杉玩这个游戏，给小杉上第一种颜色，给小小杉上第二种颜色，或者相反，都是可爱的上色方案，总共两种。