Yotsugi spielte mit einem Gitter $A$ der Höhe $h$ und Breite $w$, das anfangs mit Nullen gefüllt war, indem sie die folgenden 2 Operationen in einer beliebigen Reihenfolge anwandte:

• Wähle Werte $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) sowie ein Vorzeichen $+$ oder $-$ und ändere die Werte $A_{i,j}, A_{i,j+1}, A_{i+1,j}, A_{i+1,j+1}$ entsprechend in $A_{i,j} \pm 2, A_{i,j+1} \pm 1, A_{i+1,j} \pm 1, A_{i+1,j+1} \pm 2$, wobei $\pm$ durch das gewählte Vorzeichen ersetzt wird. Hierbei betrachtet Yotsugi $A_{h,j}$ als äquivalent zu $A_{0,j}$ und $A_{i,w}$ als äquivalent zu $A_{i,0}$. Mit anderen Worten: Sie behandelt ihr Gitter wie einen Torus.
• Wähle Werte $i, j$ ($0 \le i \le h - 1, 0 \le j \le w - 1$) sowie ein Vorzeichen $+$ oder $-$ und ändere die Werte $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}$ entsprechend in $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$, wobei $\pm$ durch das gewählte Vorzeichen ersetzt wird. Wie bei der vorherigen Operation behandelt Yotsugi das Gitter wie einen Torus.

Für ein besseres Verständnis der Operationen siehe den Abschnitt „Hinweis“.

Am nächsten Tag wurde das Gitter von der feuerspeienden Nacktschnecke gefressen, und nun fragt sich Yotsugi, wie viele mögliche Gitter sie hätte erhalten können, wenn nach Abschluss aller Operationen alle Werte $A_{i,j}$ im Intervall $[0, k]$ liegen. Beachte, dass während Yotsugi die Operationen ausführte, die Werte $A_{i,j}$ auch negativ sein oder $k$ überschreiten durften. Da die Antwort groß sein kann, hilf ihr, sie modulo $10^9 + 9$ zu bestimmen.

Eingabe

Die erste Zeile enthält 3 ganze Zahlen $h, w, k$ ($3 \le h, w \le 1\,000$, $1 \le k \le 10^9$) — die Größe des Gitters und den maximal möglichen Wert im Gitter.

Ausgabe

Gib die Antwort auf das Problem modulo $10^9 + 9$ aus.

Beispiele

Eingabe 1

3 3 1

Ausgabe 1

2

Eingabe 2

4 4 52

Ausgabe 2

972950693

Eingabe 3

7 10 123

Ausgabe 3

93519598

Hinweis

Wenn wir beispielsweise eine $4 \times 4$-Matrix hätten, könnten wir die Operationen auf folgende Weise anwenden:

Anwenden der ersten Operation mit dem Vorzeichen $-$.

Anwenden der zweiten Operation mit dem Vorzeichen $+$.

Anwenden der ersten Operation mit dem Vorzeichen $+$.

Anwenden der ersten Operation mit dem Vorzeichen $+$.

Und da alle Werte in $[0, 42]$ liegen, ist dies eine der Matrizen, die im zweiten Beispiel gezählt werden sollen.