Yotsugi đang chơi với một lưới $A$ có chiều cao $h$ và chiều rộng $w$, ban đầu được điền toàn số không, bằng cách áp dụng 2 thao tác sau theo một thứ tự nào đó:

• Chọn các giá trị $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) và dấu $+$ hoặc $-$, rồi thay đổi các giá trị $A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1}$ tương ứng thành $A_{i,j} \pm 2, A_{i,j+1} \pm 1, A_{i+1,j} \pm 1, A_{i+1,j+1} \pm 2$, trong đó $\pm$ được thay bằng dấu đã chọn. Ở đây Yotsugi coi $A_{h,j}$ tương đương với $A_{0,j}$ và $A_{i,w}$ tương đương với $A_{i,0}$. Nói cách khác, cô xem lưới của mình như một mặt xuyến (torus).
• Chọn các giá trị $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) và dấu $+$ hoặc $-$, rồi thay đổi các giá trị $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}$ tương ứng thành $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$, trong đó $\pm$ được thay bằng dấu đã chọn. Giống như thao tác trước, Yotsugi xem lưới như một mặt xuyến.

Để hiểu rõ hơn về các thao tác, hãy tham khảo phần ghi chú.

Vào ngày hôm sau, lưới đã bị con sên phun lửa ăn mất, và giờ Yotsugi tự hỏi cô có thể có bao nhiêu lưới khác nhau nếu sau khi thực hiện xong các thao tác, mọi giá trị $A_{i,j}$ đều nằm trong đoạn $[0, k]$. Lưu ý rằng trong quá trình Yotsugi áp dụng các thao tác, các giá trị $A_{i,j}$ có thể âm hoặc vượt quá $k$. Vì đáp án có thể rất lớn, hãy giúp cô tìm kết quả theo modulo $10^9 + 9$.

Dữ liệu vào

Dòng đầu tiên chứa 3 số nguyên $h, w, k$ ($3 \le h, w \le 1\,000$, $1 \le k \le 10^9$) — kích thước của lưới và giá trị lớn nhất có thể có trong lưới.

Dữ liệu ra

In ra đáp án của bài toán theo modulo $10^9 + 9$.

Ví dụ

Dữ liệu vào 1

3 3 1

Dữ liệu ra 1

2

Dữ liệu vào 2

4 4 52

Dữ liệu ra 2

972950693

Dữ liệu vào 3

7 10 123

Dữ liệu ra 3

93519598

Ghi chú

Ví dụ, nếu chúng ta có một ma trận $4 \times 4$, chúng ta có thể áp dụng các thao tác theo cách sau:

Áp dụng thao tác thứ nhất với dấu $-$.

Áp dụng thao tác thứ hai với dấu $+$.

Áp dụng thao tác thứ nhất với dấu $+$.

Áp dụng thao tác thứ nhất với dấu $+$.

Và vì tất cả các giá trị đều nằm trong $[0, 42]$, đây là một trong những ma trận mà bạn được yêu cầu đếm ở ví dụ thứ hai.