Yotsugi var að leika sér með grind $A$ af hæð $h$ og breidd $w$, sem upphaflega var fyllt með núllum, með því að beita eftirfarandi 2 aðgerðum í einhverri röð:

• Veldu gildi $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) og formerki $+$ eða $-$, og breyttu gildunum $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$ í samræmi við það, þar sem $\pm$ er skipt út fyrir valda formerkið. Hér lítur Yotsugi svo á að $A_{h,j}$ jafngildi $A_{0,j}$ og $A_{i,w}$ jafngildi $A_{i,0}$. Með öðrum orðum lítur hún á grindina sína sem kleinuhring (torus).
• Veldu gildi $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) og formerki $+$ eða $-$, og breyttu gildunum $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$ í samræmi við það, þar sem $\pm$ er skipt út fyrir valda formerkið. Eins og í fyrri aðgerðinni lítur Yotsugi á grindina sem kleinuhring.

Til að auðvelda skilning á aðgerðunum má skoða athugasemdakaflann.

Daginn eftir át eldspúandi snigillinn grindina og nú veltir Yotsugi fyrir sér hversu margar mögulegar grindur hún gæti hafa haft ef öll gildin $A_{i,j}$ lágu á bilinu $[0, k]$ eftir að hún lauk við að beita aðgerðunum. Athugið að á meðan Yotsugi var að beita aðgerðunum gátu gildin $A_{i,j}$ verið neikvæð eða farið yfir $k$. Þar sem svarið getur verið stórt skaltu hjálpa henni að finna það módúló $10^9 + 9$.

Inntak

Fyrsta línan inniheldur 3 heiltölur $h, w, k$ ($3 \le h, w \le 1\,000$, $1 \le k \le 10^9$) — stærð grindarinnar og hæsta mögulega gildi í grindinni.

Úttak

Prentið svarið við verkefninu módúló $10^9 + 9$.

Dæmi

Inntak 1

3 3 1

Úttak 1

2

Inntak 2

4 4 52

Úttak 2

972950693

Inntak 3

7 10 123

Úttak 3

93519598

Athugasemd

Til dæmis, ef við hefðum $4 \times 4$ fylki gætum við beitt aðgerðunum á eftirfarandi hátt:

Fyrri aðgerðinni beitt með formerkinu $-$.

Seinni aðgerðinni beitt með formerkinu $+$.

Fyrri aðgerðinni beitt með formerkinu $+$.

Fyrri aðgerðinni beitt með formerkinu $+$.

Og þar sem öll gildin liggja á bilinu $[0, 42]$ er þetta eitt af fylkjunum sem þú átt að telja í öðru sýnidæminu.