Một trò chơi được cho trên một dãy có độ dài \(N\), ban đầu được lấp đầy bằng các số \(0\). Trong trò chơi, chúng ta tô màu các vị trí trong dãy bằng một loạt các thao tác, và chúng ta có thể dừng tô màu sau bất kỳ thao tác nào.

Thao tác tô màu thứ X được mô tả bằng quy trình sau:

• Chúng ta chọn một vị trí chứa \(0\).
• Chúng ta quyết định: – Tô vị trí đã chọn bằng \(-1\). – Tô vị trí đã chọn bằng màu \(X\) và tiếp tục tô các vị trí liền kề bên trái bằng màu \(X\). Chúng ta dừng tô khi gặp một vị trí có giá trị khác \(0\) (mà chúng ta không tô) hoặc khi ra khỏi giới hạn của dãy.

Hai trò chơi được coi là tương đương nếu, trong các dãy cuối cùng của chúng, chúng ta có thể đổi tên các màu lớn hơn 0, tức là, nếu có một ánh xạ song ánh sao cho:

• Các màu sau khi ánh xạ vẫn lớn hơn \(0\).
• Mỗi màu nhận chính xác một nhãn mới.
• Sau khi ánh xạ, cả hai dãy giống hệt nhau.

Ví dụ về các trò chơi tương đương là:

• \([1, 1, -1, 2, -1, 3, 0]\)
• \([3, 3, -1, 1, -1, 2, 0]\)

vì có một ánh xạ màu (màu \(1\) thành màu \(3\), màu \(2\) thành màu \(1\), màu \(3\) thành màu \(2\)) sao cho tất cả các điều kiện trên được thỏa mãn.

Có \(Q\) cập nhật được cho, trong đó với mỗi cập nhật, chúng ta hoán đổi tất cả các số \(0\) với \(-1\) và tất cả \(-1\) với \(0\) trong khoảng \([L, R]\) trong dãy.

Sau mỗi cập nhật, in ra số \(K\), số lượng trò chơi khác nhau có thể chơi với số lượng thao tác tùy ý sao cho không có hai trò chơi nào tương đương. Vì \(K\) rất lớn, hãy in kết quả theo modulo \(10^9 + 7\).

Dữ liệu vào

• Dòng đầu tiên chứa \(2\) số tự nhiên \(N, Q\) \((1 \le N \le 10^{18}, 1 \le Q \le 10^5)\), biểu thị số ô trong dãy và số lượng cập nhật.
• Trong \(Q\) dòng tiếp theo, có hai số tự nhiên, \(L\) và \(R\) \((1 \le L, R \le N)\), chỉ ra các vị trí mô tả cập nhật từ bài toán.

Dữ liệu ra

• Trong dòng thứ \(i\) của \(Q\) dòng tiếp theo, in ra phần dư của phép chia số \(K\) cho \(10^9 + 7\) sau mỗi cập nhật.

Chấm điểm

Input 1

1 2
1 1
1 1

Output 1

1
3

Input 2

3 2
2 2
1 3

Output 2

9
3

Input 3

57 2
13 39
6 42

Output 3

130653412
804077942

Giải thích ví dụ đầu tiên: Sau cập nhật đầu tiên, dãy bằng [-1]. Chúng ta không thể thực hiện bất kỳ thao tác nào trên nó, vì vậy số trò chơi tối đa chúng ta có thể chơi là 1. Sau cập nhật thứ hai, dãy bằng [0]. Từ dãy [0], sử dụng các thao tác được mô tả trong bài toán, chúng ta có thể tạo các dãy [0], [1], và [-1]. Chúng ta thấy rằng không có cặp dãy nào trong số này là tương đương, vì vậy số trò chơi tối đa chúng ta có thể chơi là 3.