34325번 - 정사각형의 개수

문제

한 변의 길이가 $N$인 정사각형이 있다. 이 정사각형에는 특별한 성질이 있다. 바로 모서리를 제외한 테두리 부분에 1ドル⨯1$ 크기의 정사각형이 추가된다는 것이다.

처음에는 $N⨯N$ 크기의 정사각형이 존재하며, 모서리를 제외한 테두리 바깥쪽에 1ドル⨯1$ 크기의 정사각형들이 덧붙여진다. 이는 1ドル⨯1$ 크기의 정사각형이 더 이상 덧붙여질 공간이 없어질 때까지 반복된다. 이해를 돕기 위해 아래 사진을 확인하자.

정사각형의 한 변의 길이 $N$이 주어지고 해당 정사각형에서 1ドル⨯1$ 크기의 정사각형 생성이 끝난 뒤, 최종 모양에 포함된 ${i⨯i}$ 크기의 정사각형의 개수를 $a_i$ $({i}={1, 2, \cdots, N})$라고 할 때, $a_i⨯K^i$의 합을 출력하시오.

입력

첫째 줄에 정수 $N,ドル $K$가 공백으로 구분되어 주어진다. $(1\le N \le 1,000円,000円; 1\le K \le 100)$

출력

최종 모양에 포함된 ${i⨯i}$ 크기의 정사각형의 개수를 $a_i$ $({i}={1, 2, \cdots, N})$라고 할 때, $a_i⨯K^i$의 합을 1ドル,000円,000円,007円$로 나눈 나머지를 출력한다.

제한

힌트