색칠한 괄호

올바른 괄호 문자열은 다음 규칙으로 정의한다.

• 빈 문자열은 올바른 괄호 문자열이다.
• $S$가 올바른 괄호 문자열이면 $(S)$도 올바른 괄호 문자열이다. 즉 올바른 괄호 문자열의 앞에 여는 괄호를 붙이고 뒤에 닫는 괄호를 붙여도 올바른 괄호 문자열이다.
• $S$와 $T$가 올바른 괄호 문자열이면 $ST$도 올바른 괄호 문자열이다. 즉 올바른 괄호 문자열을 이어 붙여도 올바른 괄호 문자열이다.

어떤 사람이 괄호 문자열을 아주 좋아한다. 그런데 괄호를 한 종류만 써 온 것이 너무 재미없어서, 서로 구별할 수 있는 $K$개의 색을 괄호에 칠하기로 했다. 색이 $i$인 여는 괄호는 색이 $i$인 닫는 괄호하고만 짝을 이룬다. 예를 들어 $K = 3$이고 빨강, 초록, 파랑을 쓰기로 했다면 위 정의의 두 번째 규칙이 이렇게 늘어난다.

• $S$가 올바른 괄호 문자열이면 빨강 괄호로 감싼 $(S)$, 초록 괄호로 감싼 $(S)$, 파랑 괄호로 감싼 $(S)$가 모두 올바른 괄호 문자열이다. 한 쌍을 이루는 여는 괄호와 닫는 괄호의 색은 언제나 같다.

$K$가 더 늘어나면 구별 가능한 색을 더 추가해서 같은 방식으로 정의를 넓히면 된다.

문자열을 뒤집는다는 것은 거울에 비친 모양대로 다시 적는다는 뜻이다. 즉 문자의 순서를 거꾸로 하고, 각 괄호를 같은 색의 반대 방향 괄호로 바꾼다. 색은 그대로 남는다. 색이 하나뿐일 때 (())()를 뒤집으면 ()(())가 된다. 이 문자열은 자기 자신과 뒤집은 문자열이 다르므로 세면 안 된다. ()(())()는 뒤집어도 그대로 ()(())()이므로 세어야 한다.

$K$가지 색의 괄호 $2N$개로 만든 올바른 괄호 문자열 중에서, 자기 자신과 자기 자신을 뒤집은 문자열이 같은 것의 개수를 구하라.

첫째 줄에 괄호의 개수를 정하는 $N$과 괄호에 칠할 색의 가짓수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 10^6$, $1 \le K \le 10^6$)

$K$가지 색의 괄호 $2N$개로 올바른 괄호 문자열을 만들었을 때, 자기 자신과 자기 자신을 뒤집은 문자열이 같은 것의 개수를 출력한다. 이 수는 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

$N = 2$, $K = 2$일 때 조건을 만족하는 문자열은 6개다. 두 색을 1과 2로 적고 색을 아래 첨자로 표시하면 다음과 같다.

$(_1(_1)_1)_1$, $(_1(_2)_2)_1$, $(_2(_1)_1)_2$, $(_2(_2)_2)_2$, $(_1)_1(_1)_1$, $(_2)_2(_2)_2$