P16836 [MX-X29-T7] Mirror

There is a mirror box with $n$ rows and $m$ columns, for a total of $nm$ cells. In each cell, you may choose to place a mirror, or leave it empty. If a mirror is placed, it lies diagonally in the cell from the lower-left corner to the upper-right corner, i.e., it looks like `/`. Both sides of the mirror reflect light. You may choose any one of the $2(n+m)$ ports on the boundary of the box, shoot a laser into the box perpendicular to the boundary, and observe from which port the laser finally exits. The ports are numbered as follows: * The top boundary is numbered from left to right as $1,2,\dots,m$. * The right boundary is numbered from top to bottom as $m+1,m+2,\dots,m+n$. * The bottom boundary is numbered from right to left as $m+n+1,m+n+2,\dots,2m+n$. * The left boundary is numbered from bottom to top as $2m+n+1,2m+n+2,\dots,2(n+m)$. When entering from the top boundary, the ray goes downward. When entering from the right boundary, it goes leftward. When entering from the bottom boundary, it goes upward. When entering from the left boundary, it goes rightward. Given $n,m$, you need to find how many possible complete experiment outcomes there are. That is, shoot a laser from each of the $2(n+m)$ ports, and record the exit port of each ray. Different complete experiment outcomes are considered different configurations. Output the answer modulo $998244353$.

The first line contains an integer $T$, denoting the number of test cases. Then follow $T$ test cases. Each test case is formatted as follows: One line contains two integers $n,m$.

For each test case, output one integer per line, denoting the number of possible complete experiment outcomes modulo $998244353$.

$1\le \sum n,\sum m\le 10^6$. | Subtask ID | Score | $\sum n,\sum m\le$ | |:-:|:-:|:-:| | $1$ | $10$ | $5$ | | $2$ | $10$ | $100$ | | $3$ | $20$ | $5000$ | | $4$ | $30$ | $2\times 10^5$ | | $5$ | $30$ | $10^6$ | Translated by ChatGPT 5