Ex - Constrained Tree Degree

AtCoder

IDabc303_h

Time5000ms

Memory256MB

Difficulty—

You are given an integer $N$ and a set $S=\lbrace S_1,S_2,\ldots,S_K\rbrace$ consisting of integers between $1$ and $N-1$. Find the number, modulo $998244353$, of trees $T$ with $N$ vertices numbered $1$ through $N$ such that: * $d_i\in S$ for all $i\ (1\leq i \leq N)$, where $d_i$ is the degree of vertex $i$ in $T$. ## Constraints * $2\leq N \leq 2\times 10^5$ * $1\leq K \leq N-1$ * $1\leq S_1 < S_2 < \ldots < S_K \leq N-1$ * All values in the input are integers. ## Input The input is given from Standard Input in the following format: $N$ $K$ $S_1$ $\ldots$ $S_K$ [samples]

Samples

Input #1

4 2
1 3

Output #1

4

A tree satisfies the condition if the degree of one vertex is $3$ and the others' are $1$. Thus, the answer is $4$.

Input #2

10 5
1 2 3 5 6

Output #2

68521950

Input #3

100 5
1 2 3 14 15

Output #3

888770956

Print the count modulo $998244353$.

API Response (JSON)

{
  "problem": {
    "name": "Ex - Constrained Tree Degree",
    "description": {
      "content": "You are given an integer $N$ and a set $S=\\lbrace S_1,S_2,\\ldots,S_K\\rbrace$ consisting of integers between $1$ and $N-1$. Find the number, modulo $998244353$, of trees $T$ with $N$ vertices numbered ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc303_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an integer $N$ and a set $S=\\lbrace S_1,S_2,\\ldots,S_K\\rbrace$ consisting of integers between $1$ and $N-1$.\nFind the number, modulo $998244353$, of trees $T$ with $N$ vertices numbered ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments