象棋

非大一年级-提高题

时间限制：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)\)

注意取模。