eolymp
bolt
Try our new interface for solving problems
Məsələlər

İki palindromun konkatenasi

İki palindromun konkatenasi

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

n uzunluğunda bir dizi oluşturmanın yollarını bulun. Bu dizi, k Latin harfi kullanılarak oluşturulur (alfabe boyutu k) ve iki boş olmayan palindromun birleştirilmesiyle oluşur.

Giriş verilənləri

İki pozitif tam sayı n ve k~(1 \le n \le 10^5, 1 \le k \le 26).

Çıxış verilənləri

Verilen dizenin oluşturulması için yol sayısını yazdırın. Cevabı 10^9 + 7 ile modüler olarak yazdırın.

Nümunə

İlk test durumunda, bir harf (a örneği için) kullanılarak oluşturulan 4 uzunluğundaki dizi için üç yol bulunabilir: a + aaa, aa + aa, aaa + a.

Giriş verilənləri #1
4 1
Çıxış verilənləri #1
3
Giriş verilənləri #2
3 2
Çıxış verilənləri #2
8