암호

KOI 웹사이트의 암호는 영문 알파벳 대문자 N개로 이루어진다. 암호에는 알파벳 순서로 처음 K개의 문자만 쓸 수 있다. 예를 들어 K=5이면 A, B, C, D, E만으로 암호를 만든다. 같은 문자가 여러 번 나와도 되고, 한 번도 안 나와도 된다.

최근 연구로 두 문자열이 암호에 유난히 자주 나타난다는 사실이 밝혀졌다. 그 두 문자열은 ABCBC와 ABABC이다. 해커가 이 정보를 이용할 수 있으므로, 두 문자열 중 어느 쪽도 연속한 부분 문자열로 포함하지 않는 암호를 안전한 암호라고 부른다. 여기서 ABCBC와 ABABC는 알파벳 A, B, C를 그대로 이어 붙인 문자열이고, 다른 문자로 만든 같은 모양의 반복은 해당하지 않는다.

예를 들어 N=6, K=3일 때 두 문자열 중 하나를 포함하는 암호는 다음 12가지다.

• ABCBCA, ABCBCB, ABCBCC, AABCBC
• BABCBC, CABCBC, ABABCA, ABABCB
• ABABCC, AABABC, BABABC, CABABC

만들 수 있는 암호는 모두 $3^6 = 729$가지이므로 안전한 암호는 $729 - 12 = 717$가지다.

암호의 길이 N과 문자의 가지 수 K가 주어질 때, 안전한 암호의 개수를 구하는 프로그램을 작성하시오.

첫 줄에 암호의 길이 N과 문자의 가지 수 K가 공백을 사이에 두고 주어진다. $5 \le N \le 1{,}000{,}000$, $3 \le K \le 26$이다.

안전한 암호의 개수를 1,000,000,009로 나눈 나머지를 한 줄에 출력한다. 계산 도중의 값이 32비트 정수 범위를 넘을 수 있으니 64비트 정수를 쓴다.