Monotone OR

AtCoder

IDarc198_e

Time7000ms

Memory256MB

Difficulty—

You are given a set $S = \lbrace s_1,s_2,\dots,s_M \rbrace$ of non-negative integers between $0$ and $2^N - 1$ (inclusive). You start with a non-negative integer $x = 0$. Find the number, modulo $998244353$, of ways to reach $x = 2^N$ by performing the following operation any number of times: * Choose an integer $i$ with $1 \le i \le M$, and replace $x$ with $(x\ \mathrm{OR}\ s_i) + 1$. Here, $\mathrm{OR}$ denotes the bitwise logical OR. ## Constraints * $1 \le N \le 24$ * $1 \le M \le \min(2^N,2 \times 10^{5})$ * $0 \le s_1 < s_2 < \dots < s_M < 2^N$ ## Input The input is given from Standard Input in the following format: $N$ $M$ $s_1\ s_2\ \dots\ s_M$ [samples]

Samples

Input #1

2 2
1 2

Output #1

5

Let $(i, k)$ denote the transition when an operation chooses $i$ and results in $x = k$. There are five ways that satisfy the conditions:

*   $(1,2) \rightarrow (1,4)$
*   $(1,2) \rightarrow (2,3) \rightarrow (1,4)$
*   $(1,2) \rightarrow (2,3) \rightarrow (2,4)$
*   $(2,3) \rightarrow (1,4)$
*   $(2,3) \rightarrow (2,4)$

Even if the sequence of values of $x$ is identical, ways that differ in the choices of $i$ are counted separately.

Input #2

5 10
3 5 8 9 11 16 17 23 27 28

Output #2

242816764

Input #3

24 32
673802 709603 941436 987977 1288854 1448514 1890649 2031791 2194398 3531579 3540682 4352378 4676427 5094869 5243789 6064976 6412917 7164733 8403938 9123034 10396333 10558625 10726446 12263566 12421464 12503511 12676340 14032527 14268967 14669703 15823827 16285412

Output #3

508425421

API Response (JSON)

{
  "problem": {
    "name": "Monotone OR",
    "description": {
      "content": "You are given a set $S = \\lbrace s_1,s_2,\\dots,s_M \\rbrace$ of non-negative integers between $0$ and $2^N - 1$ (inclusive). You start with a non-negative integer $x = 0$. Find the number, modulo $9982",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 7000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc198_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a set $S = \\lbrace s_1,s_2,\\dots,s_M \\rbrace$ of non-negative integers between $0$ and $2^N - 1$ (inclusive).\nYou start with a non-negative integer $x = 0$. Find the number, modulo $9982...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments