Alice最近沉迷于一款名为Sirtet的游戏。
在Sirtet,玩家被给予$$$n \times m$$$ 网格。最初,$$$a_{i,j}$$$ 立方体堆叠在单元格 $$$(i,j)$$$ 中。如果两个单元共用一条边,则称为相邻单元。玩家可以进行以下操作:
- 在两个相邻的单元格中堆叠一个立方体;
- 将两个立方体堆叠在一个单元格中。
上述立方体的高度相同。
这是游戏的插图。右侧的状态是通过对左侧的状态执行上述操作之一而获得的,并且由于操作而添加了灰色立方体。
玩家的目标是使用上述操作使所有单元格的高度相同(即每个单元格中具有相同数量的立方体)。
然而,爱丽丝发现,在某些起始网格上,无论她使用什么策略,她都可能永远无法达到目标。因此,她想知道初始网格的数量使得
- $$$L \le a_{i,j} \le R$$$ 对于所有 $$$1 \le i \le n$$$、$$$1 \le j \le m$$$;
- 玩家可以使用上述操作达到目标。
请帮助爱丽丝。请注意,答案可能很大,请输出所需的值模 $$$998,244,353$$$。
输入
唯一的一行包含四个整数 $$$n$$$、$$$m$$$、$$$L$$$ 和 $$$R$$$ ($$$1\le n,m,L,R \le 10^9$$$、$$$L \le R$$$、$$$n \cdot m \ge 2$$$)。
输出
输出一个整数,表示所需答案对 $$$998,244,353$$$ 取模。
示例
输入 #1
2 2 1 1
输出 #1
1
输入 #2
1 2 1 2
输出 #2
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$$$。