Problem Description

During the repair work by the Laboratory IT Department, workers need to replace damaged floor tiles in a corridor. The corridor has size $2 \times n$ meters. The workers have an unlimited supply of tiles of two sizes: $1 \times 2$ meters and $1 \times 1$ meter. In addition, a $1 \times 2$ tile can be rotated by $90$ degrees, so it can be placed either along the corridor or perpendicular to it.

The workers have already started the repair and have placed $k$ tiles of size $1 \times 1$ meters at certain positions. To finish the repair, the project manager needs to prepare a plan for the remaining work. He wants to know how many ways there are to tile the remaining cells. This number should be computed modulo $10^9 + 7$.

Task: Write a program that, given the corridor length $n$ and the positions of the already placed tiles, determines the number of ways to tile the remaining cells and outputs the result.

Input Format

The first line of the input file contains two integers: $n$ — the length of the corridor, and $k$ — the number of already placed $1 \times 1$ tiles ($1 \leq n \leq 100,000$, $0 \leq k < 2n$). The next $k$ lines contain two integers $x_i$ and $y_i$, meaning that the $i$-th tile is placed at meter $x_i$ of the corridor, in row $y_i$ ($1 \leq x_i \leq n$, $1 \leq y_i \leq 2$).

Output Format

The output file should contain one integer — the number of ways to tile the remaining cells of the corridor, modulo $10^9 + 7$.

2 0

7

3 0

22

3 1
2 1

8

Hint

Figure 1. All tiling methods in the first sample.

Figure 2. All tiling methods in the third sample.

The already placed tiles are marked in gray.

Grading System and Subtask Description

Subtask 1 (20 points)

• $1 \leq n \leq 8$, $k = 0$.
• You get points only if all tests pass.

Subtask 2 (20 points)

• $1 \leq n \leq 1000$, $k = 0$.
• You get points only if all tests pass.

Subtask 3 (20 points)

• $1 \leq n \leq 100,000$, $k = 0$.
• You get points only if all tests pass.

Subtask 4 (40 points)

• $1 \leq n \leq 100,000$, $1 \leq k \leq 2n$.
• This subtask has $20$ tests. Each test is worth $2$ points, and each test is scored independently.

Translation source: GPT 5.2.

Translated by ChatGPT 5