EA Enigma

어느 조용한 토요일 오후, 요시프가 노트북을 열었을 때 한 앱을 끄지 않았다는 사실을 알아챘다. 수수께끼 게임이었다는 것을 깨닫고, 그는 한 번 플레이해 보기로 했다.

규칙은 간단하다. 숨겨진 단어를 맞혀야 한다. 단어의 길이는 $N$이며, 글자는 1부터 $K$까지의 번호로 표시된다. 플레이어가 단어를 추측하면 게임은 단어의 어느 위치가 올바르게 맞았는지 알려준다. 플레이어가 단어를 맞히면 게임이 끝난다. 게임의 결과는 단어를 맞히기까지 시도한 횟수이다.

요시프는 궁금한 것이 많아서 도움을 청한다. 요시프가 최적으로 플레이하고 숨겨진 단어가 무작위로 선택되었을 때, 게임 결과의 기댓값을 구하라.

결과를 분수 $\frac{p}{q}$로 나타내면, $p \cdot q^{-1} \bmod {10^9 + 7}$을 출력하라. (이 값은 동치인 분수 표현이 무엇이든 같다는 것이 알려져 있다.)

첫 줄에 자연수 $N$과 $K$가 주어진다 ($1 \le N \le 10^6$, $1 \le K \le 10^9$).

구한 결과를 한 줄에 출력한다.

세 번째 예제에 대한 설명이다. 기댓값은 $\frac{1}{8} + 2 \cdot \frac{7}{8} = \frac{15}{8}$이다. 따라서 $15 \cdot 8^{-1} \bmod {10^9 + 7} = 875000008$이다.