Password

A password on the KOI website is a string of N uppercase English letters. Only the first K letters of the alphabet may appear in it. For example, if K=5, a password is built from A, B, C, D, and E alone. A letter may repeat, and a letter may be missing entirely.

Recent research found that two strings turn up in passwords far more often than anything else. Those two strings are ABCBC and ABABC. A hacker can use that information, so a password is called safe when it contains neither of the two strings as a contiguous substring. Here ABCBC and ABABC are the letters A, B, and C written out in that order. The same shape built from other letters does not count.

For example, when N=6 and K=3, exactly 12 passwords contain one of the two strings.

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

There are $3^6 = 729$ possible passwords in all, so $729 - 12 = 717$ of them are safe.

Given the password length N and the letter count K, write a program that counts the safe passwords.

The first line contains the password length N and the letter count K, separated by a space. $5 \le N \le 1{,}000{,}000$ and $3 \le K \le 26$.

Print the number of safe passwords modulo 1,000,000,009 on one line. An intermediate value can exceed the range of a 32-bit integer, so use 64-bit integers.