Ştamplarla rəsm əsərləri#10425
Bessinin ixtiyarında uzunluğu vahid olan bir zolaq kətan var və o, onu rəngləmək niyyətindədir. Lakin o, heç cür fırça əldə edə bilməyib. Bunun əvəzinə onun müxtəlif rəngli rezin möhürü var və hər birinin eni vahiddir. Qarşısında açılan imkanlardan heyrətə gələn Bessi möhürləri müəyyən ardıcıllıqla kətana basaraq neçə müxtəlif şəkil yarada biləcəyini dəqiq bilmək istəyir.
Möhürdən istifadə etmək üçün Bessi əvvəlcə onu kətanın tam olaraq ardıcıl vahidi ilə üst-üstə salmalıdır. Möhür kətanın uclarından kənara çıxa bilməz, həmçinin vahidlərin hissələrini örtə bilməz. Yerləşdirildikdən sonra möhür örtdüyü vahidi öz rənginə boyayır. İstənilən möhürdən bir neçə dəfə, bir dəfə istifadə etmək və ya heç istifadə etməmək olar. Lakin Bessi işini bitirdiyi anda kətanın hər bir vahidi ən azı bir dəfə rənglənmiş olmalıdır.
Bessiyə yarada biləcəyi müxtəlif şəkillərin sayını 10^9 + 7 modulu üzrə tapmaqda kömək edin. Eyni görünən iki şəkil, möhürləmə əməliyyatlarının müxtəlif ardıcıllıqları ilə alınmış olsa belə, eyni şəkil hesab olunur.
Üç tam ədəd , və k~(1 \le n \le 10^6, 1 \le m \le 10^6, 1 \le k \le n).
Mümkün şəkillərin sayını 10^9 + 7 modulu üzrə çap edin.
Nümunə 1
Nümunədə A və B rəngli iki möhür var və mümkün şəkillər bunlardır: AAA, AAB, ABB, BAA, BBA və BBB.