Equivalence Sequence Operation

We are given an integer sequence \(a_1, a_2, \ldots, a_n\) where initially each \(a_i \in \{-1,0\}\) and, in fact, every \(a_i=0\). You can perform the following operation any number of times (possibly zero):

Let the current operation be the \(x\text{-th}\) operation. First, choose an index \(i\) with \(1 \le i \le n\) such that \(a_i=0\) (if no such index exists, you cannot perform an operation). Then choose one of the following two options:

• Option 1: Set \(a_i \gets -1\) and terminate the current operation.
• Option 2: Set \(a_i \gets x\) (a positive integer). If \(i \ge 2\) and \(a_{i-1}=0\), update \(i \gets i-1\) and repeat the two-option choice. (Note that if in the next step you also choose to assign \(a_{i-1} \gets x\), then you have \(a_{i-1}=a_i\).)

After performing an arbitrary number of operations, you obtain a resulting sequence \(a\). Two sequences \(a\) and \(b\) are defined to be equivalent if there exists a bijection \(f:\{-1,0,1,2,\ldots\}\to \{-1,0,1,2,\ldots\}\) such that:

• \(f(-1)=-1\) and \(f(0)=0\);
• For every positive integer \(i\), \(f(i) > 0\);
• \(\big[f(a_1), f(a_2), \ldots, f(a_n)\big] = [b_1, b_2, \ldots, b_n]\).

In other words, the actual positive labels assigned during the operations are irrelevant as long as the pattern of which positions become \(0\), \(-1\), or positive is maintained (up to renaming of the positive labels).

---

Initially, every \(a_i=0\). Then you are given \(q\) queries. Each query provides two integers \(l\) and \(r\) and toggles the values in the segment \(a_l, a_{l+1}, \ldots, a_r\) simultaneously, where every \(0\) becomes \(-1\) and every \(-1\) becomes \(0\).

After each query, consider the current sequence as the initial sequence for the operations described above. Your task is to compute the number of non-equivalent result sequences that can be generated, modulo \(10^9+7\).

Important Observation:

An operation, when applied to a contiguous block of zeros, converts a chosen contiguous segment into a pattern: if the segment has length \(t \ge 1\), then the leftmost cell is set to \(-1\) (by eventually choosing Option 1) and the remaining \(t-1\) cells (if any) are set to a positive number (by choosing Option 2 one or more times). Let \(f(L)\) denote the number of ways to process a contiguous block of zeros of length \(L\). It can be shown that

[ f(0)=1, \quad f(L)=f(L-1)+\sum_{i=0}^{L-1} f(i) \quad \text{for } L\ge 1. ]

Thus, if the current sequence (after a toggle query) splits into several contiguous segments of zeros, the total number of non-equivalent outcomes is

[ \prod_{\text{segment}} f(\text{length}). ]

Output the result modulo \(10^9+7\) after each query.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 2000)\), representing the length of the sequence and the number of queries, respectively.

Each of the next \(q\) lines contains two integers \(l\) and \(r\) \((1 \le l \le r \le n)\), representing a query.

outputFormat

After each query, output a single integer on a new line: the number of non-equivalent result sequences modulo \(10^9+7\).

sample

5 3
2 4
1 3
4 5

4
10
13

</p>