Snuke's Kyoto Trip

AtCoder

IDarc192_e

Time2000ms

Memory256MB

Difficulty—

You are given integers $W,H,L,R,D,U$. A town of Kyoto is on the two-dimensional plane. In the town, there is exactly one block at each lattice point $(x,y)$ that satisfies all of the following conditions. There are no blocks at any other points. * $0\leq x\leq W$ * $0\leq y\leq H$ * $x<L$ or $R<x$ or $y<D$ or $U<y$ Snuke traveled through the town as follows. * First, he chooses one block and stands there. * Then, he performs the following operation any number of times (possibly zero): * Move one unit in the positive direction of the $x$\-axis or the positive direction of the $y$\-axis. However, the point after moving must also have a block. Print the number, modulo $998244353$, of possible paths that Snuke could have taken. ## Constraints * $0\leq L\leq R\leq W\leq 10^6$ * $0\leq D\leq U\leq H\leq 10^6$ * There is at least one block. * All input values are integers. ## Input The input is given from Standard Input in the following format: $W$ $H$ $L$ $R$ $D$ $U$ [samples]

Samples

Input #1

4 3 1 2 2 3

Output #1

192

The following are examples of possible paths. Here, a path is represented by listing the lattice points visited in order.

*   $(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)$

There are $192$ possible paths.

Input #2

10 12 4 6 8 11

Output #2

Input #3

192 25 0 2 0 9

Output #3

675935675

Do not forget to print the number of paths modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Snuke's Kyoto Trip",
    "description": {
      "content": "You are given integers $W,H,L,R,D,U$. A town of Kyoto is on the two-dimensional plane. In the town, there is exactly one block at each lattice point $(x,y)$ that satisfies all of the following conditi",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc192_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given integers $W,H,L,R,D,U$.\nA town of Kyoto is on the two-dimensional plane.\nIn the town, there is exactly one block at each lattice point $(x,y)$ that satisfies all of the following conditi...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments