좋은 트리의 개수

좋은 트리는 다음 두 조건을 만족하는 트리다.

• 노드는 $k \times n$개이고 $0$번부터 $k \times n - 1$번까지 번호가 붙어 있다.
• $0 \le i, j < k \times n$이고 $i / k = j / k$인 두 노드 $i$, $j$는 서로 인접하지 않는다. 여기서 $/$는 정수 나눗셈이라서 $7 / 2 = 3$이다.

두 번째 조건은 번호를 앞에서부터 연속한 $k$개씩 끊어 $n$개의 묶음으로 나눴을 때, 같은 묶음에 속한 두 노드를 잇는 간선은 없다는 뜻이다. 나머지 노드 쌍은 간선으로 이어도 된다.

노드에는 번호가 붙어 있으므로 간선 집합이 다른 두 트리는 서로 다른 트리로 센다.

$n$과 $k$가 주어졌을 때, 좋은 트리의 개수를 세는 프로그램을 작성하시오.

첫째 줄에 $n$ ($1 \le n \le 10^5$)과 $k$ ($1 \le k \le 3$)가 공백으로 구분되어 주어진다.

좋은 트리의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.