Time Limit: 2000 MS    Memory Limit: 131072 K 


Description

An array a[1], a[2], ... a[k*n] is called a k-multipermutation if each number between 1 and n, inclusive, occurs exactly k times in it. A k-multipermutation a is called unfriendly if no two adjacent elements in it are equal. For example, the 2-multipermutation (1, 2, 3, 2, 1, 3) is unfriendly, but (1, 2, 2, 3, 1, 3) is not. You are given ints n and k. Return the number of unfriendly k-multipermutations of size n. The answer can be quite large, so return it modulo 10^9+7.

Input

There are many test cases. For each case there is only one line contains two integers n and k. n will be between 1 and 20, inclusive. k will be between 1 and 5, inclusive.

Output

For each test case output the answer on a single line.

Sample Input

3 2 2 4 5 1

Sample Output

30 2 120

Source

TopCoder