كانت Yotsugi تلعب بشبكة $A$ ارتفاعها $h$ وعرضها $w$، مملوءة في البداية بالأصفار، وذلك بتطبيق العمليتين التاليتين بترتيب ما:

• اختر القيمتين $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) والإشارة $+$ أو $-$، وغيّر القيم $A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1}$ إلى $A_{i,j} \pm 2, A_{i,j+1} \pm 1, A_{i+1,j} \pm 1, A_{i+1,j+1} \pm 2$ على الترتيب، حيث يُستبدل $\pm$ بالإشارة المختارة. تعتبر Yotsugi هنا أن $A_{h,j}$ مكافئ لـ $A_{0,j}$ وأن $A_{i,w}$ مكافئ لـ $A_{i,0}$. بعبارة أخرى، فهي تعامل شبكتها على أنها طارة (torus).
• اختر القيمتين $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) والإشارة $+$ أو $-$، وغيّر القيم $A_{i,j}, A_{i,j+1}, A_{i,j+2}, A_{i+1,j}, A_{i+1,j+1}, A_{i+1,j+2}, A_{i+2,j}, A_{i+2,j+1}, A_{i+2,j+2}$ إلى $A_{i,j} \pm 2, A_{i,j+1} \pm 5, A_{i,j+2} \pm 2, A_{i+1,j} \pm 5, A_{i+1,j+1} \pm 5, A_{i+1,j+2} \pm 5, A_{i+2,j} \pm 2, A_{i+2,j+1} \pm 5, A_{i+2,j+2} \pm 2$ على الترتيب، حيث يُستبدل $\pm$ بالإشارة المختارة. وكما في العملية السابقة، تعامل Yotsugi الشبكة على أنها طارة.

لفهم العمليات بشكل أسهل، راجع قسم الملاحظات.

في اليوم التالي، أكلت البزاقة النافثة للنار الشبكة، وتتساءل Yotsugi الآن عن عدد الشبكات الممكنة التي كان يمكن أن تحصل عليها إذا كانت جميع القيم $A_{i,j}$ بعد انتهائها من تطبيق العمليات تقع في المجال $[0, k]$. لاحظ أنه أثناء تطبيق Yotsugi للعمليات، كان من الممكن أن تكون القيم $A_{i,j}$ سالبة أو أن تتجاوز $k$. وبما أن الإجابة قد تكون كبيرة، ساعدها في إيجادها باقي قسمة على $10^9 + 9$.

الإدخال

يحتوي السطر الأول على 3 أعداد صحيحة $h, w, k$ ($3 \le h, w \le 1\,000$، $1 \le k \le 10^9$) — أبعاد الشبكة وأكبر قيمة ممكنة في الشبكة.

الإخراج

اطبع إجابة المسألة بباقي القسمة على $10^9 + 9$.

أمثلة

الإدخال 1

3 3 1

الإخراج 1

2

الإدخال 2

4 4 52

الإخراج 2

972950693

الإدخال 3

7 10 123

الإخراج 3

93519598

ملاحظة

على سبيل المثال، إذا كانت لدينا مصفوفة بحجم $4 \times 4$، فيمكننا تطبيق العمليات بالطريقة التالية:

تطبيق العملية الأولى بالإشارة $-$.

تطبيق العملية الثانية بالإشارة $+$.

تطبيق العملية الأولى بالإشارة $+$.

تطبيق العملية الأولى بالإشارة $+$.

وبما أن جميع القيم تقع في $[0, 42]$، فهذه إحدى المصفوفات المطلوب عدّها في المثال الثاني.