CF1332E.Height All the Same

Alice has got addicted to a game called Sirtet recently.

In Sirtet, player is given an $n \times m$ grid. Initially $a_{i,j}$ cubes are stacked up in the cell $(i,j)$. Two cells are called adjacent if they share a side. Player can perform the following operations:

• stack up one cube in two adjacent cells;
• stack up two cubes in one cell.

Cubes mentioned above are identical in height.

Here is an illustration of the game. States on the right are obtained by performing one of the above operations on the state on the left, and grey cubes are added due to the operation.

Player's goal is to make the height of all cells the same (i.e. so that each cell has the same number of cubes in it) using above operations.

Alice, however, has found out that on some starting grids she may never reach the goal no matter what strategy she uses. Thus, she is wondering the number of initial grids such that

• $L \le a_{i,j} \le R$ for all $1 \le i \le n$, $1 \le j \le m$;
• player can reach the goal using above operations.

Please help Alice with it. Notice that the answer might be large, please output the desired value modulo $998,244,353$.

爱丽丝最近迷上了一款名为 Sirtet 的游戏。

在 Sirtet 中，玩家会得到一个 $n \times m$ 的网格。初始时，单元格 $(i,j)$ 上堆叠了 $a_{i,j}$ 个方块。若两个单元格共享一条边，则称它们为相邻。玩家可以执行以下操作：

• 在两个相邻的单元格中各堆叠一个方块；
• 在某一个单元格中堆叠两个方块。

上述所有方块高度完全相同。

下图展示了该游戏的一个示例：右侧的状态是通过对左侧状态执行上述任一操作而得到的，灰色方块即为本次操作所添加的方块。

玩家的目标是通过上述操作，使所有单元格的高度一致（即每个单元格中的方块数量相等）。

然而，爱丽丝发现，对于某些初始网格，无论采用何种策略，她都无法达成目标。因此，她想知道满足如下条件的初始网格数量：

• 对所有 $1 \le i \le n$、$1 \le j \le m$，均有 $L \le a_{i,j} \le R$；
• 玩家可通过上述操作达成目标。

请帮助爱丽丝解决该问题。注意答案可能很大，请将结果对 $998\,244\,353$ 取模后输出。

The only line contains four integers $n$, $m$, $L$ and $R$ ($1\le n,m,L,R \le 10^9$, $L \le R$, $n \cdot m \ge 2$).

唯一一行包含四个整数 $n$、$m$、$L$ 和 $R$（$1\le n,m,L,R \le 10^9$，$L \le R$，$n \cdot m \ge 2$）。

Output one integer, representing the desired answer modulo $998,244,353$.

输出一个整数，表示所求答案对 $998,244,353$ 取模的结果。

In the first sample, the only initial grid that satisfies the requirements is $a_{1,1}=a_{2,1}=a_{1,2}=a_{2,2}=1$. Thus the answer should be $1$.

In the second sample, initial grids that satisfy the requirements are $a_{1,1}=a_{1,2}=1$ and $a_{1,1}=a_{1,2}=2$. Thus the answer should be $2$.

在第一个样例中，唯一满足要求的初始网格是 $a_{1,1}=a_{2,1}=a_{1,2}=a_{2,2}=1$。因此答案应为 $1$。

在第二个样例中，满足要求的初始网格有 $a_{1,1}=a_{1,2}=1$ 和 $a_{1,1}=a_{1,2}=2$。因此答案应为 $2$。