#P17880. Grid Problem

Grid Problem

Yotsugi 有一个高为 hh、宽为 ww 的整数网格 AA,最初所有元素均为 00。她可以按任意顺序进行任意多次以下两种操作,也可以不进行操作。

网格是环形的:所有行下标对 hh 取模,所有列下标对 ww 取模。以下使用从 00 开始的下标。

每次操作选择位置 (i,j)(i,j)(0≤i<h0\le i<h,0≤j<w0\le j<w),并选择符号 s∈{+1,−1}s\in\{+1,-1\}。

  1. 将以 (i,j)(i,j) 为左上角的 2×22\times2 区域,分别加上矩阵

    s(2112).s\begin{pmatrix}2&1\\1&2\end{pmatrix}.
  2. 将以 (i,j)(i,j) 为左上角的 3×33\times3 区域,分别加上矩阵

    s(252555252).s\begin{pmatrix}2&5&2\\5&5&5\\2&5&2\end{pmatrix}.

一次操作中的所有格子必须使用同一个符号。区域跨越边界时按上述取模规则处理。

她想知道:经过这些操作后,能得到多少种不同的网格,使最终每个元素都在 [0,k][0,k] 内?

操作过程中,元素可以为负数,也可以大于 kk;只有最终网格受到 [0,k][0,k] 的限制。 两个最终网格只要有一个位置的值不同,就视为不同。

输出答案对 109+910^9+9 取模的结果。

输入格式

一行三个整数 h,w,kh,w,k。

输出格式

输出一个整数,表示答案对 109+910^9+9 取模的结果。

数据范围

3≤h,w≤10003\le h,w\le1000,1≤k≤1091\le k\le10^9。

样例

3 3 1
2

样例说明

满足要求的最终网格是全零网格和全一网格。