لدى Bessie شريط قماش بطول $N$ وحدة ($1 \leq N \leq 10^6$) وتريد رسمه، لكنها لم تتمكن من الحصول على فرش. بدلًا منها لديها $M$ أختام مطاطية بألوان مختلفة ($1 \leq M \leq 10^6$)، عرض كل منها $K$ وحدات ($1 \leq K \leq 10^6$). مندهشة من الاحتمالات، تريد معرفة العدد الدقيق للرسومات المختلفة التي يمكنها إنشاؤها بختم القماش بترتيب ما.

يجب محاذاة الختم مع $K$ وحدات متجاورة بالضبط. لا يمكن أن يتجاوز طرفي القماش أو يغطي أجزاء من الوحدات. يصبغ الوحدات الـ $K$ المغطاة بلونه. يمكن استخدام كل ختم مرات عدة أو مرة واحدة أو عدم استخدامه. لكن عند انتهاء Bessie يجب أن تكون كل وحدة قد طليت مرة واحدة على الأقل.

ساعد Bessie في إيجاد عدد الرسومات المختلفة بترديد $10^9 + 7$. الرسومات المتطابقة في الشكل الناتجة عن تسلسلات ختم مختلفة تعد الرسم نفسه.

الإدخال

يحتوي السطر الوحيد على ثلاثة أعداد صحيحة $N$ و$M$ و$K$. مضمون أن $K \leq N$.

الإخراج

عدد صحيح واحد: عدد الرسومات الممكنة بترديد $10^9 + 7$.

أمثلة

الإدخال 1

3 2 2

الإخراج 1

6

ملاحظة

إذا كان لونا الختمين A وB، فالرسومات الممكنة AAA وAAB وABB وBAA وBBA وBBB.

المهام الفرعية

في $75\%$ على الأقل من حالات الإدخال، $N,K \leq 10^3$.

مؤلف المسألة: Dhruv Rohatgi