EOJ Monthly 2021.5 Sponsored by TuSimple

A. 数列对

单点时限: 1.0 sec

内存限制: 265 MB

有一张 $N\times M$ 的数表,记第 $i$ 行第 $j$ 列的数为 $a_{i,j}$,满足 $0\le a_{i,j}\le K$。

定义数列 $A,B$ 表示:

  • $A_i=a_{i,1}\land a_{i,2}\land\cdots\land a_{i,M}(1\le i\le N)$
  • $B_j=a_{1,j}\lor a_{2,j}\lor\cdots\lor a_{N,j}(1\le j\le M)$

其中 $\land$ 和 $\lor$ 分别表示按位与、按位或。

给定 $N,M,K$,求满足 $A_i,B_j\le K$ 的二元有序数列对 $(A,B)$ 的数量 ,使得可以反过来构造出数表 $a$。

答案对 $998244353$ 取模。

输入格式

第一行:三个整数 $N,M$ 和 $K$。

输出格式

输出一行一个整数,表示答案。

样例

Input
2 2 2
Output
15
Input
3 3 5
Output
615
Input
7 10 20
Output
329564051

提示

样例$1$解释:例如,$A={1,0}$,$B={1,1}$ 是一组合法的解,可以构造数表:$a_{1,1}=a_{1,2}=a_{2,2}=1,\ a_{2,1}=0$。

数据范围:

对于 $20\%$ 的数据:$N,M,K\leq 10$;

对于 $40\%$ 的数据:$N,M\leq 10^7,\ \ K\leq 10^5$。

对于 $100\%$ 的数据:$2\leq N,M\leq 10^{18},\ \ 1\leq K\leq 5\times 10^5$。