Solving XOR-Puzzles

AtCoder

IDs8pc_3_c

Time1000ms

Memory256MB

Difficulty—

### Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01) Snuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are distinct. He made a sequence $b$, but actually, he is not remembered it. However, he is remembered a few things about sequence $b$. * All elements in $b$ are distinct. * All elements in $b$ is in $a$. * $b_1 \\oplus b_2 \\oplus \\cdots \\oplus b_r = k$. ($r$ is length of sequence $b$) \[$\\oplus$ means XOR\] For example, if $a = { 1, 2, 3 }$ and $k = 1$, he can make $b = { 1 }, { 2, 3 }, { 3, 2 }$. He wants to restore sequence $b$, but he says that there are too many ways and he can't restore it. Please calculate the ways to make $b$ and help him. Since the answer can be large, print the answer modulo $1,000,000,007$. ## Input The input is given from Standard Input in the following format: > $n \\ k$ $a_1 \\ a_2 \\ \\cdots \\ a_n$ [samples]

Samples

Input #1

3 1
1 2 3

Output #1

3

You can make 3 patterns: $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$

Input #2

3 10
8 7 5

Output #2

6

You can make 6 patterns: $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$.

Input #3

25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125

Output #3

235924722

Please output answer mod $1,000,000,007$.

API Response (JSON)

{
  "problem": {
    "name": "Solving XOR-Puzzles",
    "description": {
      "content": "### Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01) Snuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are di",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "s8pc_3_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "### Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01)\n\nSnuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are di...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments