Йоцуги бастапқыда нөлдермен толтырылған биіктігі $h$ және ені $w$ болатын $A$ торымен ойнап отырып, келесі 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$ таңдалған таңбамен алмастырылады. Мұнда Йоцуги $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$ таңдалған таңбамен алмастырылады. Алдыңғы амалдағыдай, Йоцуги торды тор беті ретінде қарастырады.

Амалдарды оңайырақ түсіну үшін ескертпе бөлімін қараңыз.

Келесі күні торды от шашатын шырышты ұлу жеп қойды, енді Йоцуги барлық амалдарды орындап болғаннан кейін барлық $A_{i,j}$ мәндері $[0, k]$ аралығында жатса, онда қанша мүмкін тор шығатынын білгісі келеді. Йоцуги амалдарды қолдану барысында $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]$ аралығында жатқандықтан, бұл екінші мысалда санау сұралған матрицалардың бірі болып табылады.