Description

You have an $n$-ring puzzle, which has the same structure as the well-known nine-ring puzzle.

The figure above shows a nine-ring puzzle.

As the name suggests, an $n$-ring puzzle has a long bar, with $n$ rings on it that affect each other.

We number these $n$ rings: the ring closest to the head of the bar is ring $1$, then ring $2$, and so on; the ring closest to the tail of the bar is ring $n$.

Define $f_i$ as the state of ring $i$, where $f_i = 1$ means the ring is on the bar, and $f_i = 0$ means the ring is not on the bar.

Define removing/installing a ring as flipping the ring’s state, i.e. changing the state from $1$ to $0$ or from $0$ to $1$.

The legal rules for removing/installing rings are:

1. Ring $1$ can always be removed/installed alone.
2. Ring $k+1$ can be removed/installed alone if and only if $f_k = 1$ and for all $i < k$, we have $f_i = 0$.
3. If $f_1 = f_2$, then rings $1$ and $2$ can be removed/installed together.

Now you need to solve the following problem: given the initial state of an $n$-ring puzzle, find the minimum number of legal remove/install operations needed to completely remove the $n$-ring puzzle.

Input Format

The amount of data in this problem is large, so a special input format 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:

Line $i + 2$ contains two integers $len_{i}, st_{i}$, meaning that we continuously append $len_{i}$ rings of state $st_{i}$ to the tail of the initial $n$-ring puzzle.

Output Format

Output one integer, the minimum number of remove/install operations needed to remove the $n$-ring puzzle starting from the given state.

Since the answer may be very large, you only need to output the result modulo $1201201201$.

4
3
1 1
1 0
2 1

7

15
4
5 1
2 1
4 0
4 1

15424

3
3
1 1
1 0
1 1

5

Hint

This problem uses bundled tests, with O2 optimization enabled.

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

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

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

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

$\text{Subtask 5 (30 pts)}:$ no special constraints.

For all testdata, $1 \le n \le 10^{18}$, $1 \le m \le 10^5$, $st_{i} \in \{0, 1\}$, $len_{i} \ge 1$.

It is guaranteed that $\sum\limits_{i=1}^m len_{i} = n$.

Sample #1 Explanation

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

One way to finish with the minimum number of legal remove/install operations is:

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.

Extra Notes

In this problem, the 3rd remove/install rule for the $n$-ring puzzle is not mentioned in most nine-ring puzzle instructions, but it is indeed a real and feasible operation.

Translated by ChatGPT 5