Mật khẩu

Vòng chung kết cuộc thi lập trình thi đấu ACM-ICPC tổ chức tại vương quốc Alpha có $m$ đội tham gia dự thi. Ban tổ chức bố trí rất nhiều phòng máy tính để các đội làm bài thi, các phòng máy tính được đánh số thứ tự $0,1,2,3,\dots$, các máy tính trong mỗi phòng được đánh số thứ tự $1,2,3,\dots$. Mỗi máy tính đều có mật khẩu để đăng nhập vào hệ thống nộp bài trực tuyến: nếu một đội thi tại phòng máy số $n$ và ngồi ở vị trí máy tính số $k$ thì mật khẩu đăng nhập vào hệ thống là giá trị của biểu thức

$$\rho (n,k)=\{\begin{array}{cc}1,\hfill & \text{nếu }n=0,\hfill \\ {\displaystyle \frac{k·(\rho (0,k)+\rho (1,k)+\dots +\rho (n-1,k))}{n}},\hfill & \text{nếu }n\ge 1,\hfill \end{array}$$

lấy theo mô đun ${10}^9+7$. Phép chia trong công thức là phép chia số thực thông thường; có thể chứng minh $\rho (n,k)$ luôn là số nguyên dương, và mật khẩu là số dư của số nguyên đó khi chia cho ${10}^9+7$.

Yêu cầu: Cho danh sách $m$ đội thi, biết đội thứ $i$ thi tại phòng máy số $n_i$ và tại máy số $k_i$. Hãy tìm mật khẩu đăng nhập hệ thống của mỗi đội trong danh sách đã cho.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $m$ ($1\le m\le 2·{10}^5$).
• Dòng thứ $i$ trong $m$ dòng tiếp theo chứa hai số nguyên $n_i$ và $k_i$ ($1\le n_i,k_i\le 2·{10}^5$).

Hai số liên tiếp trên cùng dòng được ghi cách nhau bởi dấu cách.

Dữ liệu ra

Gồm $m$ số nguyên, mỗi số ghi trên một dòng, là mật khẩu đăng nhập tương ứng với mỗi đội theo thứ tự trong dữ liệu vào (tức $\rho (n_i,k_i)$ theo mô đun ${10}^9+7$).

Ràng buộc

• $1\le m\le 2·{10}^5$.
• $1\le n_i,k_i\le 2·{10}^5$.

Subtasks

• $20\%$ số test: $m\le 2·{10}^5$, $n_i\le 3$, $k_i\le 2·{10}^5$.
• $20\%$ số test: $m\le 2·{10}^5$, $n_i+k_i\le 50$.
• $30\%$ số test: $m\le 5000$, $n_i,k_i\le 5000$.
• $30\%$ số test còn lại: không có ràng buộc gì thêm.

Ví dụ