#216190. [ICPC 2019 NAIPC] XOR Sequences

Suppose you are given two integers, and . You are also given a list of distinct integers , with . For each number from to , you’ve found the number such that has a maximum bitwise- with . That is, for all , ( means bitwise-).

Now, consider the reverse problem. Given , , and the sequence , count the number of sequences of distinct integers that could have generated that sequence from the above algorithm. Two sequences are different if there is some such that in one sequence is different from in the other sequence. Output this count modulo .

Each test case will begin with a line with two space-separated integers () and (), where is the length of the sequence, and is the length of the sequences.

Each of the next lines will contain a single integer (). These are the values of the sequence , in order. Every value from to inclusive will appear at least once.

Output a single integer, which is the number of sequences which could have generated the sequence from the above algorithm, modulo .

样例输入 1

3 6
1
1
2
2
3
4
5
6

样例输出 1

4

样例输入 2

2 3
1
2
1
3

样例输出 2

0

样例输入 3

3 8
1
2
3
4
5
6
7
8

样例输出 3

1