Yotsugi は最初すべてゼロで埋められた高さ $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$ は選んだ符号に置き換えられる。Yotsugi は $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$ は選んだ符号に置き換えられる。前の操作と同様に、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$ 行列がある場合、次のように操作を適用できます。
符号 $-$ で 1 番目の操作を適用する。
符号 $+$ で 2 番目の操作を適用する。
符号 $+$ で 1 番目の操作を適用する。
符号 $+$ で 1 番目の操作を適用する。
すべての値が $[0, 42]$ に収まっているため、これは 2 番目の入力例で数えるべき行列の 1 つです。