Cho mảng \(a\) gồm \(n\) phần tử, lúc đầu tất cả các phần tử của mảng \(a\) đều có giá trị là \(1\). Cho \(q\) truy vấn, truy vấn thứ \(i\) có dạng \(x_i, y_i\) yêu cầu thay đổi giá trị của phần tử thứ \(x_i\) thành \(y_i\). Sau mỗi truy vấn, cho \(x = \prod_{k=1}^n a_k\). Nhiệm vụ của bạn là in ra số ước nguyên dương của \(x\), vì số lượng ước của số \(x\) rất lớn nên in ra dưới dạng modulo cho \(10^9 + 7\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n, q\) (\(1 \leq n, q \leq 10^5\)).
• \(q\) dòng tiếp theo, dòng thứ \(i\) chứa \(2\) số \(x_i, y_i\) (\(1 \leq x_i \leq n, 1 \le y_i \le 10^5\)) là truy vấn thứ \(i\).

Output

• Gồm \(q\) dòng là đáp án cho \(q\) truy vấn.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \le a_i \leq 2\) (với mọi \(1 \le i \le n\)).
• Subtask \(2\) (\(40\%\) số điểm): \(1 \le q, n \leq 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 3
1 3
1 4
2 5

2
3
6