P16836 【MX-X29-T7】Mirror

有一个镜子盒，它包含 $n$ 行 $m$ 列，共 $nm$ 个方格。每个方格中可以选择放置一面镜子，也可以不放置镜子。 若放置镜子，则镜子在方格内从左下角到右上角呈对角线方向排列，即形如 `/`。镜子的两侧都会反射光。 你可以从镜子盒外围的 $2(n+m)$ 个端口中任选一个，垂直于边界向镜子盒内发射一道激光，并观测激光最终从哪个端口射出。 端口编号方式如下： * 上边界从左到右编号为 $1,2,\dots,m$； * 右边界从上到下编号为 $m+1,m+2,\dots,m+n$； * 下边界从右到左编号为 $m+n+1,m+n+2,\dots,2m+n$； * 左边界从下到上编号为 $2m+n+1,2m+n+2,\dots,2(n+m)$。 从上边界射入时，光线向下进入；从右边界射入时，光线向左进入；从下边界射入时，光线向上进入；从左边界射入时，光线向右进入。 给定 $n,m$，你需要求出一共有多少种可能的完整实验结果。 也就是说，对于所有 $2(n+m)$ 个端口分别射入激光，记录每条光线的射出端口。不同的完整实验结果视为不同方案。 答案对 $998244353$ 取模。

第一行包含两个整数 $T$，表示数据组数。 接下来包含 $T$ 组数据。 每组数据的格式如下： 一行包含两个整数 $n,m$。

对于每组数据，输出一行一个整数，表示可能的完整实验结果数量对 $998244353$ 取模后的值。

$1\le \sum n,\sum m\le 10^6$。 | 子任务编号|分值| $\sum n,\sum m\le$ | |:-:|:-:|:-:| | $1$ | $10$ | $5$ | | $2$ | $10$ | $100$ | | $3$ | $20$ | $5000$ | | $4$ | $30$ | $2\times 10^5$ | | $5$ | $30$ | $10^6$ |