djb 的二维动规

题目描述

djb 最近学习了简单的动态规划《跳格子》

题目很简单，有一个 $W * H$ 的棋盘，左下角是 $(1,1)$，右上角是 $(W,H)$

djb 一开始处于左下角 $(1,1)$ 处，要跳到右上角 $(W,H)$，每次 djb 可以向右或者向上跳一格，问方案数

现在 djb 觉得这道题没什么意思，自己加强了一下

现在 djb 如果处于坐标 $(x,y)$，他每次可以选择跳到以 $(x,y)$ 为左下角的边长为 $K+1$ 的正方形中的任意一个位置作为目的地，但是不能原地不动

现在 djb 想拿这道题考考你，请你计算一下有多少种方案数。

输入格式

输入包含三个正整数 $W,H,K$。

输出格式

输出一个整数表示答案，由于方案数过大，你需要将答案对 $998244353$ 进行取模。

数据规模

对于 $30$ 的数据：$W,H\leq8$；

对于 $60$ 的数据：$K=1$；

对于 $100$ 的数据：$1\leq W,H,K\leq 2000$。

样例输入

3 3 2

样例输出

26