시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB124978477.778%

문제

한 변의 길이가 $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$로 나눈 나머지를 출력한다.

예제 입력 1

1 25

예제 출력 1

25

예제 입력 2

2 9

예제 출력 2

117

예제 입력 3

1000000 5

예제 출력 3

404223949

출처

University > 금오공과대학교 > 2025 KUMOH ASK CONTEST C번