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}$ กล่าวอีกนัยหนึ่ง เธอมองตารางกริดของเธอเป็นทอรัส (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]$ นี่จึงเป็นหนึ่งในเมทริกซ์ที่คุณต้องนับในตัวอย่างที่สอง