Modifications

AtCoder

IDagc067_b

Time3000ms

Memory256MB

Difficulty—

You have an integer sequence $a=(a_1,a_2,\cdots,a_N)$ of length $N$. All elements are initially $0$. You are given an integer $C$ and $M$ intervals $([L_1,R_1],[L_2,R_2],\cdots,[L_M,R_M])$. You will choose a permutation $p$ of $(1,2,\cdots,M)$ and an integer sequence $w=(w_1,w_2,\cdots,w_M)$ of length $M$. Here, $1\le w_i\le C$ must hold. Then, you will do $M$ modifications. The $i$\-th modification is the following: * Change $a_{L_{p_i}}, \cdots, a_{R_{p_i}}$ to $w_i$. It is guaranteed that every position in $a$ is covered by at least one interval. Find the number of achievable $a$ after all modifications. Print the answer modulo $998244353$. ## Constraints * $1\le N\le 100$ * $1\le M\le\dfrac{N(N+1)}{2}$ * $1\le C<998244353$ * $1 \le L_i \le R_i \le N$ * $(L_i,R_i) \neq (L_j,R_j)$ ($i \neq j$) * Every position in $a$ is covered by at least one interval. * All input values are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $C$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_M$ $R_M$ [samples]

Samples

Input #1

Output #1

16

There are $16$ sequences that can be achieved. For example, you can achieve $a=(2,1,1,1,1)$ in the following manner:

*   Choose $p=(4,1,2,3,5)$ and $w=(1,2,1,2,1)$
*   The $1$\-st operation changes $a$ into $(1,1,1,1,1)$
*   The $2$\-nd operation changes $a$ into $(2,2,2,1,1)$
*   The $3$\-rd operation changes $a$ into $(2,1,2,1,1)$
*   The $4$\-th operation changes $a$ into $(2,1,2,1,1)$
*   The $5$\-th operation changes $a$ into $(2,1,1,1,1)$

Input #2

Output #2

258066445

API Response (JSON)

{
  "problem": {
    "name": "Modifications",
    "description": {
      "content": "You have an integer sequence $a=(a_1,a_2,\\cdots,a_N)$ of length $N$. All elements are initially $0$. You are given an integer $C$ and $M$ intervals $([L_1,R_1],[L_2,R_2],\\cdots,[L_M,R_M])$. You will c",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc067_b"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have an integer sequence $a=(a_1,a_2,\\cdots,a_N)$ of length $N$. All elements are initially $0$.\nYou are given an integer $C$ and $M$ intervals $([L_1,R_1],[L_2,R_2],\\cdots,[L_M,R_M])$.\nYou will c...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments