접미사 배열의 개수

길이가 $N$인 문자열 $S$의 접미사 배열을 이렇게 정의한다. $S$의 $i$번째 접미사는 $S$의 $i$번째 문자부터 마지막 문자까지를 잘라낸 문자열이다. 접미사 $N$개를 사전순으로 정렬한 뒤 각 접미사의 시작 위치를 차례대로 적으면 $1$부터 $N$까지의 순열이 하나 나온다. 이 순열이 $S$의 접미사 배열이다. 길이가 서로 다른 두 접미사도 사전순 대소가 항상 정해지므로 접미사 배열은 문자열마다 하나로 정해진다.

문자는 순서가 정해진 알파벳에서 고른다. 알파벳은 $M$종류를 쓰기에 충분히 크다.

길이가 $N$이고 사용한 문자의 종류가 $M$가지 이하인 문자열을 모두 모아 각각의 접미사 배열을 구했을 때, 서로 다른 배열이 몇 개인지 구하라. 두 배열 $A$와 $B$가 서로 다르다는 것은 $A[i] \neq B[i]$인 정수 $i$가 적어도 하나 있다는 뜻이다.

첫째 줄에 두 자연수 $N$, $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 10^6$)

조건을 만족하는 문자열의 접미사 배열 가운데 서로 다른 것의 개수를 $10^9 + 7$로 나눈 나머지를 한 줄에 출력한다.

$N = 4$, $M = 2$이면 서로 다른 접미사 배열이 12개다. 각 배열과 그 배열을 만드는 문자열의 예를 함께 적으면 다음과 같다.

• $[1, 2, 3, 4]$: aaab
• $[1, 2, 4, 3]$: aabb
• $[1, 4, 3, 2]$: abbb
• $[2, 3, 4, 1]$: baab
• $[2, 4, 1, 3]$: babb
• $[3, 1, 4, 2]$: abab
• $[3, 4, 2, 1]$: bbab
• $[4, 1, 2, 3]$: aaba
• $[4, 1, 3, 2]$: abba
• $[4, 2, 3, 1]$: baba
• $[4, 3, 1, 2]$: abaa
• $[4, 3, 2, 1]$: aaaa, baaa, bbaa, bbba, bbbb

맨 아래 줄처럼 서로 다른 문자열이 같은 접미사 배열을 만들기도 한다. 이런 배열도 한 번만 센다.