題目描述

從前，一位國王非常喜歡收集手鍊，尤其是由寶石串成的獨特手鍊。
你收到了以下情報：

• 手鍊是約干個寶石組成的序列

• 有K種目前人類可以採集的寶石

• 假如手鍊不能由約干個相同的手鍊連接成的，則稱為獨特的。

你作為國王的使者，你現在需要計算世界上有多少種長度為N的手鍊是獨特的。
您的答案應對109+7取模。

例子

以下用數字0~9表示不同的寶石：

• 101101101 不是獨特的
• 12031203 不是獨特的
• 12012012 是獨特的
• 1234123 是獨特的

輸入格式

一行 N K

輸出格式

對於給定的N和K，獨特的手鍊的數量對109+7取模後的結果。

Samples

6 2

54

原始資料

• Zero1 題號：b412
• Hydro 題號：Z1412
• Locale：zh_TW
• Display：open