Ştamplarla rəsm əsərləri
Bessi uzunluğu n olan bir kətan parçası tapıb və onu rəngləməyi planlaşdırır. Lakin, rəsm üçün fırçalar ala bilmir. Bunun əvəzinə, onun m müxtəlif rəngli rezin möhürləri var və hər möhür k vahid enindədir. Bessi, bu möhürləri müəyyən bir ardıcıllıqla kətana basaraq neçə fərqli rəsm yarada biləcəyini öyrənmək istəyir.
Möhürü istifadə etmək üçün kətanda tam olaraq k qonşu vahid tapmaq lazımdır. Möhür kətanın kənarlarından çıxa bilməz və vahidlərin bir hissəsini örtə bilməz. Möhür yerləşdirildikdən sonra k vahidi öz rəngi ilə rəngləyir. Hər hansı bir möhür bir neçə dəfə, bir dəfə və ya heç istifadə edilməyə bilər. Lakin Bessi işini bitirdikdə, kətanın hər bir vahidi ən azı bir dəfə rənglənməlidir.
Bessiyə, 10^9 + 7 moduluna görə neçə fərqli rəsm yarada biləcəyini tapmağa kömək edin. Eyni görünən, lakin fərqli möhürləmə əməliyyatları ardıcıllığı ilə yaradılmış iki rəsm eyni hesab olunur.
Giriş Məlumatları
Bir sətir üç tam ədəd n (1 ≤ n ≤ 10^6), m (1 ≤ m ≤ 10^6) və k (1 ≤ k ≤ 10^6) ehtiva edir. k ≤ n təmin edilir.
Çıxış Məlumatları
Mümkün rəsmlərin sayını 10^9 + 7 moduluna görə çıxarın.
Nümunə
Əgər iki möhür A və B rənglərinə malikdirsə, mümkün rəsmlər AAA, AAB, ABB, BAA, BBA və BBB olacaq.