Mã định danh

Một tổ chức hoạt động bí mật có \(M\) thành viên. Tổ chức có các nhóm hoạt động được đánh số \(0\), \(1\), \(2\), ..., và trong mỗi nhóm có các nhiệm vụ khác nhau đánh số \(1\), \(2\), \(3\), ... Người đứng đầu tổ chức cần lập mã định danh cho các thành viên trong tổ chức, mỗi thành viên tương ứng với một mã. Mã định danh của một thành viên thuộc nhóm \(n\) và làm nhiệm vụ \(k\) sẽ là số dư của giá trị của hàm \(f(n, k)\) khi chia cho \(10^9 + 7\), với hàm \(f(n, k)\) được định nghĩa như sau :

\(f(n, k) = 1\) nếu \(n = 0\).

\(F(n, k) = \frac{k \times (F(0, k) + F(1,k) + ... + f(n - 1, k))}{n}\), nếu \(n \geq 1.\)

Yêu cầu: Cho danh sách các thành viên, mỗi thành viên cho biết họ hoạt động trong nhóm nào và thực hiện nhiệm vụ gì, hãy xác định mã định danh của \(M\) thành viên của tổ chức đó.

Input

• Dòng đầu tiên chứa số nguyên \(M\) (\(1 \leq M \leq 2 \times 10^5\)).

• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i, k\) cách nhau bởi dấu cách (\(1 \leq i, k \leq 2 \times 10^5\)) thể hiện mỗi thành viên hoạt động với mã nhóm \(i\) và thực hiện nhiệm vụ thứ \(k\).

Output

Gồm \(M\) dòng, mỗi dòng chứa một số nguyên là mã định danh của một thành viên, theo đúng thứ tự trong danh sách đã cho ở tệp đầu vào.

Example

4
1 13
2 213
5 45
7 56789

13
22791
1906884
460782414

Scoring

• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n \leq 3\), \(k \leq 2.10^5\);
• \(20\%\) số test tương ứng với \(20\%\) số điểm của bài có : \(M \leq 2.10^5\), \(n + k \leq 65\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : \(M \leq 5.10^3\), \(n, k \leq 5.10^3\);
• \(30\%\) số test tương ứng với \(30\%\) số điểm của bài có : không có ràng buộc gì thêm.