17007번 - XOR Sequences 다국어

문제

Suppose you are given two integers, m and n. You are also given a list of n distinct integers x₁, x₂, . . . , x_n, with 0 ≤ x_i ≤ 2^m−1. For each number y from 0 to 2^m−1, you’ve found the number p_y such that x_py has a maximum bitwise-XOR with y. That is, y ⊕ x_py >y ⊕ x_i for all i=1..n, i ≠ p_y (⊕ means bitwise-XOR).

Now, consider the reverse problem. Given m, n, and the sequence p₀, p₁, . . . , p_2^m−1, count the number of sequences of distinct integers x₁, x₂, . . . , x_n that could have generated that p sequence from the above algorithm. Two x sequences are different if there is some i such that x_i in one sequence is different from x_i in the other sequence. Output this count modulo 10⁹+7.

입력

Each test case will begin with a line with two space-separated integers m (0 ≤ m ≤ 16) and n (1 ≤ n ≤ 2^m), where 2^m is the length of the p sequence, and n is the length of the x sequences. Each of the next 2^m lines will contain a single integer p (1 ≤ p ≤ n). These are the values of the sequence p₀, p₁, . . . , p_2^m−1, in order. Every value from 1 to n inclusive will appear at least once.

출력

Output a single integer, which is the number of sequences x₁, x₂, . . . , x_n which could have generated the sequence p₀, p₁, . . . , p_2^m−1 from the above algorithm, modulo 10⁹+7.

제한

힌트