背景

备选

描述

给出一个图,图中有n组点,每组的点数相同,同为k,分组方式如下:

(1~k), (k+1~2k),(2k+1~3k)...

同一组内不能连边,其他的都是有连边的。

给定k,n,求生成树个数。

输入格式

两个用空格隔开的整数n和k。

输出格式

一个整数,表示生成树个数,Mod 10^9+7

样例输入

2 2

样例输出

4

数据范围与约定

1<=k<=3, 1<=n<=10^9