String Periodik

Deskripsi

Sebuah string dikatakan “periodik” jika terdapat sebuah string lain yang berulang-ulang secara teratur pada string tersebut lebih dari satu kali. Secara formal, sebuah string disebut periodik jika terdapat string dan sebuah bilangan asli m>1 sehingga

s= t+t+⋯+t (m kali).

Sebagai contoh, string “ababab” adalah string periodik, karena kita dapat memilih dan sehingga syarat di atas terpenuhi; string “xyzxyz” juga periodik dengan dan . Namun, string “abcabcd” dan “pqrpqrpq” keduanya bukan merupakan string periodik.

Tentukan banyaknya string yang periodik, jika diketahui bahwa panjang string tersebut adalah dan terdapat pilihan karakter yang dapat digunakan.

Format Masukan

Masukan berisi dua buah bilangan bulat, dan , yang berturut-turut menyatakan panjang string dan banyak pilihan karakter yang dapat digunakan.

Format Keluaran

Tuliskan banyaknya string yang memenuhi deskripsi di atas, modulo 1000000007 .

Penjelasan

Untuk kasus uji pertama, misalkan karakter yang diperbolehkan adalah 'a' dan 'b'. Maka, string periodik yang memenuhi ada 10 buah, yaitu "aaaaaa", "ababab", "aabaab", "abaaba", "abbabb", "baabaa", "babbab", "bbabba", "bababa", "bbbbbb".

Batasan

• 1 ≤ N ≤ 1000000000 (10^9).
• 1 ≤ K ≤ 100.

• Batasan waktu adalah 1 detik, dan batasan memori adalah 32 MB.