Alice and Bob's Binary Merge Game

Alice and Bob are playing a game on a binary sequence of length n (positions numbered from 1 to n). Initially the sequence is a 0–1 sequence. Before the game begins, Bob uses magic m times: in the i-th magic he changes the number at position a_i to v_i (either 0 or 1). That is, the initial sequence before Bob’s magic is unknown; after Bob’s magic the bits at positions a_i become v_i (if a position is never targeted, its original value remains).

After Bob’s changes, Alice and Bob take turns to operate on the resulting sequence. Alice moves first. In each move the current player picks any two adjacent numbers in the sequence and merges them into a single number using an operation allowed to him/her:

• Alice replaces the two numbers with their xor (in \(\LaTeX\): \(a\oplus b\)).
• Bob replaces the two numbers with their and (in \(\LaTeX\): \(a\land b\)).

This continues until only one number remains. If the final number is 1, then Alice wins; otherwise Bob wins.

Your task is: Given the values of n and m and the m magic modifications (positions and new values), count how many possible initial 0–1 sequences (i.e. before Bob’s modifications) will guarantee that Alice wins the game if both players play optimally. As the answer may be very large, output it modulo \(10^9+7\).

Note: You are given the positions which become fixed by Bob’s magic. The other positions may be arbitrarily 0 or 1 in the initial sequence. The game is played on the modified sequence (after Bob’s magic) and both players play optimally.

inputFormat

The first line contains two integers \(n\) and \(m\) \( (1 \le n \le 12,\; 0 \le m \le n)\) --- the length of the sequence and the number of magic modifications.

Then follow \(m\) lines. The \(i\)th of these lines contains two integers \(a_i\) and \(v_i\) \( (1 \le a_i \le n,\; v_i \in \{0,1\})\) indicating that Bob changes the number at position \(a_i\) to \(v_i\). If a position appears more than once, the last occurrence should be used.

Note: In this problem, since the optimal‐play analysis is complicated, you may assume that \(n\) is small enough (\(n\le 12\)) so that a brute force over the free positions is acceptable.

outputFormat

Output one integer, the number of possible initial sequences that lead to an Alice win (after Bob’s magic modifications are applied), modulo \(10^9+7\).

sample

1 0

1