QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 1024 MB
[-1]

# 3013. XOR Sequences

Statistics

Problem Description

Suppose you are given two integers, m and n. You are also given a list of n distinct integers x1,x2,,xn, with 0xi2m1. For each number y from 0 to 2m1, you've found the number py such that xpy has a maximum bitwise-XOR with y. That is, yxpy>yxi for all i=1n,ipy( means bitwise-XOR).

Now, consider the reverse problem. Given m,n, and the sequence p0,p1,,p2m1, count the number of sequences of distinct integers x1,x2,,xn that could have generated that p sequence from the above algorithm. Two x sequences are different if there is some i such that xi in one sequence is different from xi in the other sequence. Output this count modulo 109+7.

Input

Each test case will begin with a line with two space-separated integers m (0m16) and n(1n2m), where 2m is the length of the p sequence, and n is the length of the x sequences.

Each of the next 2m lines will contain a single integer p (1pn). These are the values of the sequence p0,p1,...,p2m1, in order. Every value from 1 to n inclusive will appear at least once.

Output

Output a single integer, which is the number of sequences x1,x2,,xn which could have generated the sequence p0,p1,,p2m1 from the above algorithm, modulo 109+7.

Samples

Sample Input 1

3 6
1
1
2
2
3
4
5
6

Sample Output 1

4

Sample Input 2

2 3
1
2
1
3

Sample Output 2

0

Sample Input 3

3 8
1
2
3
4
5
6
7
8

Sample Output 3

1