Problem Background

"During the first nine days and the second nine days, you don't move your hands; during the third nine days and the fourth nine days, you walk on ice; during the fifth nine days and the sixth nine days, you watch willows across the river;

By the seventh nine days, the river thaws, by the eighth nine days, the geese return, and by the ninth nine days plus another nine days, the oxen are plowing everywhere."

The number "nine" has always been a fascinating number in ancient times, and the problem you are about to solve is also related to "nine."

Problem Description

You have an $n$-ring, similar in structure to the well-known nine-ring puzzle.

The image above is a nine-ring puzzle.

As the name suggests, an $n$-ring consists of a long beam with $n$ rings hanging on it, each affecting the others.

We number these $n$ rings, with the ring closest to the head of the beam being the first ring, the next being the second ring, and so on... the ring closest to the end of the beam being the $n$-th ring.

Define $f_i$ to represent the state of the $i$-th ring, where $f_i = 1$ means the ring is on the beam, and $f_i = 0$ means the ring is not on the beam.

Define removing or installing a ring as inverting the state of the ring, i.e., changing the state from $1$ to $0$ or from $0$ to $1$.

The valid rules for removing or installing these rings are as follows:

1. The first ring can be removed or installed at any time.
2. The $(k+1)$-th ring can be removed or installed if and only if $f_k = 1$ and $\forall i < k$, $f_i = 0$.
3. If $f_1 = f_2$, then the first and second rings can be removed or installed together.

The problem you need to solve is: Given the initial state of an $n$-ring, find the minimum number of steps required to remove the entire $n$-ring.

Input Format

Due to the large amount of data, a special input method is used.

The first line contains a positive integer $n$.

The second line contains a positive integer $m$.

The next $m$ lines describe the initial state:

The $i + 2$-th line contains two integers $len_{i}$ and $st_{i}$, indicating that $len_{i}$ rings with state $st_{i}$ are consecutively added to the end of the initial $n$-ring.

Output Format

A single line containing one integer, representing the minimum number of steps required to remove the $n$-ring, modulo $1201201201$.

Sample Input and Output

Sample Input #1

4
3
1 1
1 0
2 1

Sample Output #1

7

Sample Input #2

15
4
5 1
2 1
4 0
4 1

Sample Output #2

15424

Sample Input #3

3
3
1 1
1 0
1 1

Sample Output #3

5

Notes

This problem uses bundled testing and O2 optimization.

$\text{Subtask 1 (10 pts)}:$ Guaranteed $1 \le n \le 20$.

$\text{Subtask 2 (15 pts)}:$ Guaranteed $1 \le n \le 1000$.

$\text{Subtask 3 (15 pts)}:$ Guaranteed that there is only one $1$ in the initial state.

$\text{Subtask 4 (30 pts)}:$ Guaranteed $1 \le n \le 10^7$.

$\text{Subtask 5 (30 pts)}:$ No special restrictions.

For all data, it is guaranteed that $1 \le n \le 10^{18}$, $1 \le m \le 10^5$, $st_{i} \in \{0, 1\}$, $len_{i} \ge 1$.

The data ensures that $\sum\limits_{i=1}^m len_{i} = n$.

Sample #1 Explanation

The sample describes a $4$-ring with an initial state of 1101.

The method to complete it with the minimum number of valid steps is as follows:

1. 1101 -> 1100
2. 1100 -> 0100
3. 0100 -> 0111
4. 0111 -> 0110
5. 0110 -> 0010
6. 0010 -> 0011
7. 0011 -> 0000

A total of $7$ steps.

Side Note

The third removal/installation rule for the $n$-ring in this problem is not mentioned in most玩法说明 for the nine-ring puzzle, but it is indeed a feasible operation!

见题面 Input 部分

见题面 Output 部分