Xoşbəxt sonluqla xoşbəxt rəsm
Polis Barışı tutduqdan sonra ona cərimə kəsdi. Barış, uzunluğu N olan bir parça kətanla qarşılaşdı (1 ≤ N ≤ 10^6) və onu boyamaq istəyir. Lakin, fırçaları olmadığı üçün, fərqli rənglərdə M ədəd rezin möhürü var (1 ≤ M ≤ 10^6), hər bir möhür K vahid genişliyindədir (1 ≤ K ≤ 10^6). Barış, bu möhürləri kətan üzərində müəyyən bir ardıcıllıqla basaraq neçə fərqli rəsm yarada biləcəyini öyrənmək istəyir. Möhürü istifadə etmək üçün, əvvəlcə onu kətan üzərində tam K qonşu vahidə uyğunlaşdırmaq lazımdır. Möhür kətanın uclarından kənara çıxa bilməz və ya vahidlərin hissələrini örtə bilməz. Bir dəfə yerləşdirildikdə, möhür örtülən K vahidləri öz rəngi ilə boyayır. Hər hansı bir möhür bir neçə dəfə, bir dəfə və ya heç istifadə edilməyə bilər. Amma Barış işini bitirdikdə, kətanın hər vahidi ən azı bir dəfə boyanmış olmalıdır. Barışa neçə fərqli rəsm yarada biləcəyini, 10^9+7 modulu ilə tapmağa kömək edin. Eyni görünən, lakin fərqli möhürləmə əməliyyatları ardıcıllığı ilə boyanmış iki rəsm eyni sayılır.
Giriş:
İlk sətirdə N, M, K ədədləri verilir. K ≤ N.
Çıxış formatı:
Tək bir tam ədəd: mümkün rəsmlərin sayı, 10^9 + 7 modulu ilə.
Birinci test nümunəsi üçün izah
Əgər iki möhürün rəngləri A və B olarsa, mümkün rəsmlər AAA, AAB, ABB, BAA, BBA və BBB olacaqdır.