← 返回题目列表

AtCoder · arc192_e

E. Snuke的京都之旅

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你整数 W,H,L,R,D,U.

京都的一个小镇位于二维平面上。

在城镇中,每个格子点恰好有一个街区 (x,y) 满足以下所有条件。其他任何点都没有块。

  • 0\leq x\leq W
  • 0\leq y\leq H
  • x<L or R<x or y<D or U<y

Snuke 穿过城镇的方式如下。

  • 首先,他选择一个方块并站在那里。
  • 然后,他执行以下操作任意次数(可能为零):
    • 向正方向移动一个单位 x- 轴或正方向 y- 轴。但移动后的点也必须有一个块。

打印数字,模数 998244353,Snuke 可能采取的路径。

约束

  • 0\leq L\leq R\leq W\leq 10^6
  • 0\leq D\leq U\leq H\leq 10^6
  • 至少有一个块。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

W H L R D U

输出

打印答案。


示例输入 1

4 3 1 2 2 3

示例输出 1

192

以下是可能路径的示例。这里,通过按顺序列出访问过的格点来表示路径。

  • (3,0)
  • (0,0)\rightarrow (1,0)\rightarrow (2,0)\rightarrow (2,1)\rightarrow (3,1)\rightarrow (3,2)\rightarrow (4,2)\rightarrow (4,3)
  • (0,1)\rightarrow (0,2)

有 192 可能的路径。


示例输入 2

10 12 4 6 8 11

示例输出 2

4519189

示例输入 3

192 25 0 2 0 9

示例输出 3

675935675

不要忘记打印路径数模数 998244353.