Tô màu dải lụa

Tại một ngôi làng cổ nổi tiếng với nghề thủ công truyền thống, lễ hội mùa xuân đang đến gần. Theo phong tục, mỗi gia đình sẽ treo một dải lụa dài trước cửa nhà như biểu tượng của may mắn và thịnh vượng.

Gia đình của Mitsuha cũng vậy, họ sẽ tự tô màu một dải lụa rồi treo trước nhà. Và năm nay, Mitsuha được giao nhiệm vụ lên kế hoạch trang trí dải lụa đó.

Khi ta trải thẳng dải lụa, nó như một đoạn thẳng có \(N\) ô, và ban đầu có một số ô đã được vẽ sẵn họa tiết. Những ô còn lại đang có màu \(0\).

Quy trình tô diễn ra như sau:

• Mitsuha chọn một cây bút có mã màu từ \(1\) đến \(10^{18}\).
• Bước tiếp theo, cô sẽ chọn một trong \(N\) ô, và tại ô đó chưa được tô màu và cũng không chứa họa tiết. Sau đó cô có một trong \(2\) lựa chọn sau: \begin itemize
• Cô vẽ hoạ tiết lên ô đó.
• Cô bắt đầu tô từ ô được chọn, sau đó kéo một đường sang trái cho đến khi cô gặp một ô có họa tiết hoặc đã được tô màu sẵn hoặc ra khỏi dải lụa. Những ô vừa tô sẽ mang màu \(i\) là mã của cây bút màu cô chọn.

\end itemize

• Quy trình tô này có thể kết thúc tại bất cừ thời điểm nào.

\begincenter

\smallVí dụ khi Mitsuha đặt bút màu đỏ tại ô \(5\), khi đó cô ấy sẽ kéo màu sang trái đến ô \(3\) - là ô có họa tiết. (X là các ô có họa tiết)
\endcenter
Lưu ý trong quy trình trên, một mã màu chỉ được chọn nhiều nhất một lần.

Mitsuha muốn được biết có bao nhiêu cách tô màu khác nhau cho dải lụa trên. \(2\) cách được gọi là khác nhau khi không tồn tại cách đánh số lại màu để tạo ra dải màu tương tự. Lưu ý, màu của các họa tiết không phân biệt.

Ví dụ xét \(2\) dải màu: \([3, 3, 1, 0]\) và \([2, 2, 3, 0]\), hai dãy trên là tương đương vì ta có cách đánh số \(3\)->\(2\), \(1\)->\(3\) để từ dãy \(1\) ta thu được dãy \(2\).

Chưa kết thúc ở đó, có \(Q\) truy vấn làm thay đổi trạng thái của một ô trong dải. Cụ thể mỗi truy vấn là \([L, R]\) các ô có chỉ số thuộc đoạn này nếu đang có họa tiết thì trở nên không có họa tiết, và ngược lại.

Được biết dải lụa ban đầu không có màu và không có họa tiết. Hãy giúp Mitsuha tìm cách giải bài toán này nhé.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\), \(Q\) \((1 \leq N \leq 10^{18},\ 1 \leq Q \leq 10^5)\) --- số lượng ô trong dải và số lần cập nhật.
• Mỗi dòng trong \(Q\) dòng tiếp theo chứa hai số nguyên dương \(L\) và \(R\) \((1 \leq L, R \leq N)\) --- mô tả đoạn cần cập nhật.

Output

• In ra \(Q\) dòng, dòng thứ \(i\) chứa một số nguyên --- phần dư khi chia số cách tô hợp lệ cho \(10^9 + 7\).

Example

1 2
1 1
1 1

1
3

3 2
2 2
1 3

9
3

100 3
10 20
15 58
1 15

318045953
998064805
390938541

Scoring

\begintabular|c|c|l|
\hline
Subtask & Điểm & Ràng buộc

\hline
1 & 30 & \(N, Q \leq 1000\)

2 & 30 & \(N \leq 10^5\)

3 & 40 & Không có ràng buộc bổ sung

\hline
\endtabular