Valentine’s Coat(coat)

成绩 0 开启时间 2012年10月10日 星期三 11:05
折扣 0.8 折扣时间 2012年10月10日 星期三 11:05
允许迟交 关闭时间 2012年10月10日 星期三 11:05

描述

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

Oh,it sounds good.

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

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

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

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

输入格式

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

输出格式

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

样例输入

2 2

样例输出

2

样例解释

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