Time Limit: 2000 MS Memory Limit: 131072 K
An array a, a, ... 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.
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.
For each test case output the answer on a single line.