Score : 1100 points
There are 2^N players, numbered 1, 2, ..., 2^N. They decided to hold a tournament.
The tournament proceeds as follows:
It is known that, the result of the match between two players can be written as follows, using M integers A_1, A_2, ..., A_M given as input:
The champion of this tournament depends only on the permutation p_1, p_2, ..., p_{2^N} chosen at the beginning. Find the number of permutation p_1, p_2, ..., p_{2^N} chosen at the beginning of the tournament that would result in Player 1 becoming the champion, modulo 10^9 + 7.
Input is given from Standard Input in the following format:
N M A_1 A_2 ... A_M
Print the answer.
2 1 3
8
Examples of p that satisfy the condition are: [1, 4, 2, 3] and [3, 2, 1, 4]. Examples of p that do not satisfy the condition are: [1, 2, 3, 4] and [1, 3, 2, 4].
4 3 2 4 6
0
3 0
40320
3 3 3 4 7
2688
16 16 5489 5490 5491 5492 5493 5494 5495 5497 18993 18995 18997 18999 19000 19001 19002 19003
816646464