象棋

非大一年级-提高题

时间限制：1s

空间限制：64MB

题目描述

假设象棋中的“马”位于$n*m$的棋盘中，初始位于 $(a,b)$ 点，问：有多少种走子方法可以使得其在 $k$ 步 以内(1~k步) 走到 $(c,d)$ 点？

若以下条件之一满足，则认为两种走子方法不同：

• 两者需要的步数不同
• 存在$i$，使得第 $i$ 步后，"马"处于的位置不同。

按照象棋规则，"马"走“日”字。即，可以一步从$(x,y)$走到$(x+dx,y+dy)$，如果$(x+dx,y+dy)$在棋盘范围内，且 $|dx|+|dy|=3$ 且 $|dx|*|dy|=2$。

由于方法数可能很多，对 $998244353$ 取模。

输入格式

一行七个正整数$n,m,a,b,c,d,k$，用空格隔开。

输出格式

一个整数表示答案，注意取模。

样例输入1

3 3 1 1 2 3 3

样例输出1

4

样例1解释

有以下四种方法：

$(1,1)\to (2,3)$

$(1,1)\to (2,3)\to (1,1)\to (2,3)$

$(1,1)\to (3,2)\to (1,1)\to (2,3)$

$(1,1)\to (2,3)\to (3,1)\to (2,3)$

样例输入2

3 3 1 1 2 2 2

样例输出2

0

样例输入3

21 23 11 18 6 1 75

样例输出3

705262804

数据范围

对于 50% 的数据，$1\le n,m \le 6,1\le k\le 10$

对于 100% 的数据，

$1\le n,m\le 30, 1\le k\le 80$

$1\le a,c\le n$

$1\le b,d\le m$

update: 保证 $(a,b) \neq (c,d)$

注意取模。