Yotsugi שיחקה עם רשת $A$ בגובה $h$ וברוחב $w$, שהייתה מלאה בתחילה באפסים, על ידי הפעלת 2 הפעולות הבאות בסדר כלשהו:

• בחר ערכים $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}$. במילים אחרות, היא מתייחסת לרשת שלה כאל טורוס.
• בחר ערכים $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]$, זוהי אחת המטריצות שאתם מתבקשים לספור בדוגמה השנייה.