1.种花

小 C 决定在他的花园里种出 $\texttt{CCF}$ 字样的图案，因此他想知道 $\texttt C$ 和 $\texttt F$ 两个字母各自有多少种种花的方案；不幸的是，花园中有一些土坑，这些位置无法种花，因此他希望你能帮助他解决这个问题。

花园可以看作有 $n\times m$ 个位置的网格图，从上到下分别为第 $1$ 到第 $n$ 行，从左到右分别为第 $1$ 列到第 $m$ 列，其中每个位置有可能是土坑，也有可能不是，可以用 $a_{i,j} = 1$ 表示第 $i$ 行第 $j$ 列这个位置有土坑，否则用 $a_{i,j} = 0$ 表示这个位置没土坑。

一种种花方案被称为 $\texttt{C-}$ **形**的，如果存在 $x_1, x_2 \in [1, n]$，以及 $y_0, y_1, y_2 \in [1, m]$，满足 $x_1 + 1 < x_2$，并且 $y_0 < y_1, y_2 \leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_2$ **行**都**不为土坑**，且只在上述这些位置上种花。

一种种花方案被称为 $\texttt{F-}$ **形**的，如果存在 $x_1, x_2, x_3 \in [1, n]$，以及 $y_0, y_1, y_2 \in [1, m]$，满足 $x_1 + 1 < x_2 < x_3$，并且 $y_0 < y_1, y_2 \leq m$，使得第 $x_1$ **行**的第 $y_0$ 到第 $y_1$ **列**、第 $x_2$ **行**的第 $y_0$ 到第 $y_2$ **列**以及第 $y_0$ **列**的第 $x_1$ 到第 $x_3$ **行**都**不为土坑**，且只在上述这些位置上种花。

样例一解释中给出了 $\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案的图案示例。

现在小 C 想知道，给定 $n, m$ 以及表示每个位置是否为土坑的值 $\{a_{i,j}\}$，$\texttt{C-}$ 形和 $\texttt{F-}$ 形种花方案分别有多少种可能？由于答案可能非常之大，你只需要输出其对 $998244353$ 取模的结果即可，具体输出结果请看输出格式部分。

**【样例 1 解释】**

四个 $\texttt{C-}$ 形种花方案为：

```plain
**1 **1 **1 **1
*10 *10 *10 *10
**0 *** *00 *00
000 000 **0 ***
```

其中 $\texttt*$ 表示在这个位置种花。注意 $\texttt C$ 的两横可以不一样长。

类似的，两个 $\texttt{F-}$ 形种花方案为：

```plain
**1 **1
*10 *10
**0 ***
*00 *00
```

**【数据范围】**

对于所有数据，保证：$1 \leq T \leq 5$，$1 \leq n, m \leq 10^3$，$0 \leq c, f \leq 1$，$a_{i,j} \in \{0, 1\}$。

| 测试点编号 | $n$ | $m$ | $c=$ | $f=$ | 特殊性质 | 测试点分值 |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $1$ | $\leq 1000$ | $\leq 1000$ | $0$ | $0$ | 无 | $1$ |
| $2$ | $=3$ | $=2$ | $1$ | $1$ | 无 | $2$ |
| $3$ | $=4$ | $=2$ | $1$ | $1$ | 无 | $3$ |
| $4$ | $\leq 1000$ | $=2$ | $1$ | $1$ | 无 | $4$ |
| $5$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | A | $4$ |
| $6$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | B | $6$ |
| $7$ | $\leq 10$ | $\leq 10$ | $1$ | $1$ | 无 | $10$ |
| $8$ | $\leq 20$ | $\leq 20$ | $1$ | $1$ | 无 | $6$ |
| $9$ | $\leq 30$ | $\leq 30$ | $1$ | $1$ | 无 | $6$ |
| $10$ | $\leq 50$ | $\leq 50$ | $1$ | $1$ | 无 | $8$ |
| $11$ | $\leq 100$ | $\leq 100$ | $1$ | $1$ | 无 | $10$ |
| $12$ | $\leq 200$ | $\leq 200$ | $1$ | $1$ | 无 | $6$ |
| $13$ | $\leq 300$ | $\leq 300$ | $1$ | $1$ | 无 | $6$ |
| $14$ | $\leq 500$ | $\leq 500$ | $1$ | $1$ | 无 | $8$ |
| $15$ | $\leq 1000$ | $\leq 1000$ | $1$ | $0$ | 无 | $6$ |
| $16$ | $\leq 1000$ | $\leq 1000$ | $1$ | $1$ | 无 | $14$ |

特殊性质 A：$\forall 1 \leq i \leq n, 1 \leq j \leq \left\lfloor \frac{m}{3} \right\rfloor$，$a_{i, 3 j} = 1$；

特殊性质 B：$\forall 1 \leq i \leq \left\lfloor \frac{n}{4} \right\rfloor, 1 \leq j \leq m$，$a_{4 i, j} = 1$；

6222: 1.种花

题目描述

输入

输出

样例输入输出

提示

题目信息

模拟

数学与数论

动态规划

贪心

字符串

排序

枚举

数组与串

深搜

高精度

循环结构

递推

递归

二分三分

宽搜

背包

质数

线段树

分治

N进制

图论

队列

最短路

堆

树

并查集

栈

状态压缩

分支结构

几何

博弈论

生成树

顺序结构

离散化

hash表

位运算

单调队列

树状数组

KMP

字典树

二分图

数学期望

AC自动机

树链剖分

差分约束

数位动态规划

函数与过程

网络流

单调栈

前缀和