30521번 - Mike Sees The Storm (Large)

Mike가 보고 있는 칠판에는 $0$이 적혀 있다. Mike는 다음과 같은 두 가지의 동작 중 하나를 선택해 반복하면서 수열을 얻고자 한다.

• 칠판에 쓰인 숫자가 $a$라 하면, 이를 지우고 $a+1$을 쓴다.
• 칠판에 쓰인 숫자가 $a$라 하면, 이를 지우고 $a-1$을 쓴다.

두 가지 동작의 순서는 상관없지만, 각각의 동작을 $N$번씩 수행해야 한다. 이때, 칠판에 쓰는 숫자를 순서대로 원소로 하는 수열을 $A_{1}, A_{2}, \cdots, A_{2N}$이라고 하자.

Mike가 진행할 수 있는 모든 순서에 대해 얻어낸 수열들 각각의 최댓값을 $K$제곱한 합을 구해보자.

이때, 답이 커질 수 있으므로 소수 $1\ 000\ 000\ 007$로 나눈 나머지를 계산하여라.

입력 첫 줄에 음이 아닌 정수 $N$과 $K$가 주어진다. ($1 \leq N \leq 1\ 000\ 000$, $1 \leq K \leq 500\ 000$)

Mike가 얻을 수 있는 모든 수열들 각각의 최댓값을 $K$제곱한 합을 출력하여라.