P11746 Dynamic Color Problem

你在和 AI 下『连子棋』！你们有黑白两个颜色的棋子。 这盘棋的规则是：双方轮流下棋，棋子放满整个棋盘后，再来统计分数。如果每有一整行或一整列颜色 **不完全相同**，那么你就获得 $1$ 分。如果每有一整行或一整列颜色 **完全相同**，那么 AI 就获得 $1$ 分。当你的分数为奇数且 AI 的分数为偶数时，那么你就胜利了！否则，AI 胜利。 你和 AI 对弈了 $T$ 局，第 $i$ 局的棋盘大小为 $n\times m $。双方每一回合都可以选择下黑或者下白，下棋的位置不能和之前重复。那么请计算棋盘最终形态的方案数使得你能获胜。 两种下棋方式不同，当且仅当最终棋盘的形态不同，即棋盘上存在一个位置，使得两种棋盘在此位置的颜色不同。答案可能很大，请对 $998244353$ 取模。

无

无

**【样例解释 $\mathbf 1$】** 对于第 $2$ 局棋盘大小 $2\times 3$ 有下列两种棋盘形式（总共 $32$ 种棋盘形式，不一一列出）：  上面两种情况，你获得 $3$ 分，AI 获得 $2$ 分，故你获胜。 --- **【数据规模与约定】** **本题开启子任务捆绑测试**。本题自动开启 O2 优化。 * Subtask 1（15 pts）：$2\leq n,m\leq 4$。 * Subtask 2（15 pts）：$2\leq n,m\leq 6$。 * Subtask 3（8 pts）：$2\leq n,m\leq 20$。 * Subtask 4（8 pts）：$2\leq n,m\leq 100$。 * Subtask 5（10 pts）：$2\leq n,m\leq 1000$。 * Subtask 6（44 pts）：$2\leq n,m\leq 10^6$。 对于所有测试点满足 $1\leq T\leq 5$，$2\leq n,m\leq 10^6$。