+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همون طور که احتمالا تا الان متوجه شدین، صالح موجود عجیبیه!! آریان با پول هایی که از رستورانش در آورده می خواد که کف سالن رستورانش رو رنگ کنه. سالن رستوران آریان از $N$ کاشی تشکیل شده، این کاشی ها به صورت پشت سر هم و به طور مرتب قرار گرفتن. صالح یک شرکت رنگ آمیزی راه انداخته و آریان می خواد این کار رو به شرکت صالح اینا بسپره. صالح از اون جایی که کلا آدم عجیبیه قوانین عجیبی هم برای رنگ کردن این راهرو داره. شرکت صالح اینا $M$ نوع رنگ مختلف داره. آریان هر بار می تونه یک بازه ی $K$ تایی از این راهرو رو انتخاب کنه و همین طور هم یک نوع رنگ خاص رو و بچه های صالح اینا، این بخش از راهرو رو رنگ می کنن. آریان می خواد بدونه که به چند طریق می تونه این راهرو رو رنگ بکنه به طوری که هر کاشی حداقل یکبار رنگ شده باشد. توجه کنید که ترتیب رنگ شدن راهرو برای آریان اهمیتی نداره و فقط به رنگ نهایی راهرو کار داره. به طور دقیق تر آریان دو حالت رو مجزا می دونه اگر در انتهای کار دو کاشی باشند که رنگشون با هم فرق داشته باشه. # ورودی ورودی شامل یک خط است و اعداد $N$ و $M$ و $K$ به شما به ترتیب داده می شوند. $$1 \le N, M, K \le 1000000$$ # خروجی شما باید تعداد روش های رنگ آمیزی رو به پیمانه ی 1000000007 خروجی دهید. ## ورودی نمونه ۱ ``` 3 2 2 ``` ## خروجی نمونه ۱ ``` 6 ```