30520번 - Mike Sees The Storm (Small)

문제

Small 버전에서는 $N$의 최댓값의 제한이 1000ドル$으로 줄어들고 $K$는 1ドル$로 고정되어 주어진다.

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,ドル $K = 1$)

출력

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

제한

힌트